More Related Content
What's hot (20)
Similar to Core–periphery detection in networks with nonlinear Perron eigenvectors (20)
Recently uploaded (20)
Core–periphery detection in networks with nonlinear Perron eigenvectors
- 1. Core–periphery detection in networks with nonlinear Perron eigenvectors Francesco Tudisco joint work with Des Higham (U. of Edinburgh)
- 2. Matrix reordering problems Clusters (communities) Bipartite (anti–communities) Lattice (small–world) Core–periphery 1
- 3. Core–periphery Borgatti, Everett, Social Networks, 1999 Core: nodes strongly connected across the whole network Periphery: nodes strongly connected only to the core Csermely, London, Wu, Uzzi, J. of Complex Networks, 2013 Rombach, Porter, Fowler, Mucha, SIAM Review, 2018 2
- 5. Core–periphery detection problem Tasks: 1. Reorder nodes to reveal core–periphery structure 2. assign coreness score to nodes 4
- 6. Setting G = (V, E) undirected, unweighted, simple graph with n nodes ... it can all be extended to directed and weighted graphs Adjacency matrix A: Aij = 1 if i and j are connected, Aij = 0 otherwise 5
- 7. Core–periphery kernel optimization Core–score vector u is such that : if ui > uj =⇒ i is closer to the core than j Our proposal: Core–score vector as solution of the following constrained core–periphery kernel optimization (P) { maximize fα(u) = ∑n i,j=1 Aijκα(ui, uj) subject to ∥u∥p = 1, u ≥ 0 with κα(x, y) = ( xα+yα 2 )1/α 6
- 8. Core-periphery kernel α large ⇒ κα(x, y) ≈ max{x, y} fα(u) = ∑ ij Aijκα(ui, uj) is large when edges Aij = 1 involve at least one node with large core-score 7
- 9. Logistic core–periphery (LCP) random model Random graph: Pr(i ∼ j) = 1 1 + e−κα(ui,uj) =: pij(u) Logistic function 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 1/(1−e−x) x Matrix of probabilities 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 8
- 10. Result 1: Connection to CP kernel Suppose we have a sample from the LCP random graph model, with nodes in arbitrary order. Find u that maximizes the likelihood ∏ i∼j pij ( u ) ∏ i̸∼j ( 1 − pij(u) ) 9
- 11. Result 1: Connection to CP kernel Suppose we have a sample from the LCP random graph model, with nodes in arbitrary order. Find u that maximizes the likelihood ∏ i∼j pij ( u ) ∏ i̸∼j ( 1 − pij(u) ) Theorem: If u is a node labeling (permutation) then the maximum likelihood problem is equivalent to max u n∑ i,j=1 Aijκα(ui, uj) (Useful for testing core–periphery detection algorithms) 9
- 12. Connection with node degrees If p = 2 and α = 1 then κ1 = arithmetic mean (P) ⇐⇒ max u≥0 ∥Au∥1 ∥u∥2 = ∥A∥2→1 and the maximizer is u = degree vector 10
- 13. Connection with eigenvector centrality If p = 1 and α = 0 then κ0 = geometric mean (P) ⇐⇒ max u≥0 uT Au uT u = ρ(A) and the maximizer is u = Perron eigenvector of A What about the general case ...... 11
- 14. Result 2: Nonlinear Perron eigenvector (P) { maximize fα(u) = ∑n i,j=1 Aij(uα i + uα j )1/α subject to ∥u∥p = 1, u ≥ 0 is a hard nonconvex optimization task 12
- 15. Result 2: Nonlinear Perron eigenvector (P) { maximize fα(u) = ∑n i,j=1 Aij(uα i + uα j )1/α subject to ∥u∥p = 1, u ≥ 0 is a hard nonconvex optimization task Theorem: If α ≥ 0 and p > max{1, α}, then • (P) has a unique solution u • u is positive if and only if no dangling nodes • u is the nonlinear Perron eigv Mα(u)u = λ u, with Mα(u) = Dα−1 u Aα(u) and Aα(u)ij = Aij uα−2 j (uα i /uα j + 1) 1−α α 12
- 16. Result 3: Computation Can we solve Mα(u)u = λ u? (Nonlinear PM) uk+1 = Mα(uk)uk k = 0, 1, 2, . . . 13
- 17. Result 3: Computation Can we solve Mα(u)u = λ u? (Nonlinear PM) uk+1 = Mα(uk)uk k = 0, 1, 2, . . . Theorem: Choose u0 > 0 and let δ = (p − α)/(p − 1), then • ∥uk+1 − uk∥∞ ≤ e−δk ∥u1 − u0∥∞ • ∥uk+1 − u∥∞ ≤ 1 δ e−δk ∥u1 − u0∥∞ Globally convergent method with linear convergence rate 13
- 18. Note on the analysis • We do not require that the objective function is convex. Instead, we use the homogeneity f(λx) = λf(x) of the objective and the constraint functions • We do not require the network to be connected (matrix to be irreducible) in order to have uniqueness and positivity • In practice we use p = 20 and α = 10 14
- 19. Computational Results We look at the following core–periphery detection methods • Rombach • Coreness • Degree • Eigenvector 15
- 20. Stochastic Block Models 1 1.2 1.4 1.6 1.8 2 k 0.5 0.6 0.7 0.8 0.9 1 Fractionofnodescorrectlyassigned Degree NSM Sim-Ann 1 1.2 1.4 1.6 1.8 2 k 0.5 0.6 0.7 0.8 0.9 1 Fractionofnodescorrectlyassigned Degree NSM Sim-Ann 0 20 40 60 80 100 Network size 10 -6 10 -4 10 -2 10 0 10 2 10 4 ExecutionTime(s) Deg NSM Sim-Ann 16
- 21. Top ten London train stations α = 0 Adjacency Eigenvector Simulated Annealing α = 10 Nonlinear Perron Eigenvect 17
- 22. Top ten London train stations Eigenvector Sim-Ann NSM King’s Cross 128.85 Embankment 26.84 King’s Cross 128.85 Farringdon 29.75 King’s Cross 128.85 Baker Str. 29.75 Euston Square 14.40 Liverpool Str. 138.95 West Ham 77.10 Barbican 11.97 Baker Str. 29.75 Liverpool Str. 138.95 Gt Port. Str. 86.60 Bank 96.52 Paddington 85.32 Moorgate 38.40 Moorgate 38.40 Stratford 129.01 Euston 87.16 Euston Square 14.40 Embankment 26.84 Baker Str. 29.75 Gloucester Road 13.98 Willesden Junct. 109.27 Liverpool Str. 138.95 Farringdon 27.92 Moorgate 38.40 Angel 22.10 West Ham 77.10 Earls Court 20.00 Total 586.09 592.70 783.48 +35% 18
- 23. Other real world datasets Degree Sim-Ann Nonlinear Eig YeastPPI n ≈ 2k Internet2006 n ≈ 25k 19
- 24. Core–periphery profiles Permutation π1, . . . , πn such that uπ1 ≤ uπ2 ≤ · · · ≤ uπn Della Rosa, Dercole, Piccardi Scientific Reports, 2013 Persistance probability of the set Sk = {π1, . . . , πk} γ(Sk) = ∑ i,j∈Sk Aij ∑ i∈Sk degree(i) Probability that a random walker who is currently in any of the nodes of Sk, remains in Sk at the next time step 20
- 25. Core–periphery profiles 0 500 1000 1500 2000 k 10−3 10−2 10−1 100 γk(x) Eig Sim-Ann CorenessDeg NSM Yeast PPI 0 5000 10000 15000 20000 k 10−4 10−3 10−2 10−1 100 Eig Sim-Ann Coreness Deg NSM Internet 2006 21
- 26. Directed networks: Enron emails dataset n ≈ 90k 22