Adam PhillippyAdam PhillippySamuel Huang` Identify a natural grouping◦ Many edges withingroups◦ Few edges betweengroups` Structure only` No attributes[Newman 2006]` Blockmodels◦ Similar connectionsCiti`Communities◦ Interconnections[Reichardt, Bornholdt 2006]` Compute betweeness for each edgell h h d lk◦ All pairs shortest paths or random walk◦ Count traversals for each edge` Remove edge with highest score` Find componentsRildidbf`Repeat until desired number of communities[Girvan, Newman 2002]` Difference from random model` For a subset of nodes s in GModularity◦ModularityQ=A−kikj⎛ ⎜ ⎞ ⎟ ∑Qs=Aij2m⎝ ⎜ ⎠ ⎟ ij∑i jAij[Newman 2006]` For some binary grouping of nodes◦ Modularity of the groupingQ1Akikj⎛ ⎜⎞ ⎟∑1()`Maximize the modularityQQ=4mAij−ij2m⎝ ⎜ ⎠ ⎟ ij∑sisj+1()`Maximize the modularity Q[Reichardt, Bornholdt 2006]` Forget ferromagnetism, spin, and all the other physics jargon. They are essentially the same thingthing.H=−Aij−γkikj⎛ ⎝⎜ ⎞ ⎠⎟ ∑δsi,sj()HAijγ2m⎝ ⎜ ⎠ ⎟ ij∑δsi,sj()Q =14mAij−kikj2m⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ∑sisj+1()4m2m⎝ ⎠ ijGraph layoutsG(n,m) → AAvi=λiIviλ1≤λ2≤L ≤λn 12nL=D−ALDA` Symmetric, positive semidefinite◦ All eigenvectors are mutually orthogonal◦ All n eigenvalues real and non-negative` Nice for graphs◦All rows sum to 0,∴existsλ1=0,v1={1,1, ,1}All rows sum to 0, ∴exists λ10, v1{1,1,…,1}◦ Multiplicity of λi=0 is number of components◦ λ2proportional to the graphs connectivity◦ v2Fiedler eigenvector used for spectral bisection[Boccaletti et al 2006]v2v3kkBij= Aij−kikj2m` Reminiscent of Laplacian2mp◦ Symmetricx All eigenvectors are mutually orthogonal◦ All rows sum to zerox Exists λ1=0, v1={1,1,…,1}x All other v must contain both +/- elements[Newman 2006]Q =14mAij−kikj2m⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ∑sisj4mj2m⎝ ⎠ ijj=1sTBs=4msBs1T()2βn∑=4muiT⋅s()βii=1∑[Newman 2006]Q∝ uiT⋅ s()2βii1n∑` Assume ordered eigenvaluesi=1g` Aim to maximize β1≥β2≥L ≥βnT◦ Set sito +1 if u1,iis positive.◦Setsito-1ifu1iis negative.u1T⋅ sSet sito 1 if u1,iis negative.[Newman 2006]` Power method◦ Iterative multiplication, normalization◦ Start with random v, stop on convergenceBvk` Sparse matrix for speedvk+1=BvkBvkBv = Av−kkT⋅ v()2m2m[Newman 2006][Newman 2006]` Split for greatest modularity gain◦ Recurse until modularity can’t be improved[Girvan, Newman 2002]` Spectral◦ Laplacian◦Modularity` Edge removal◦ Betweeness◦MinCut◦Modularity` Q or H OptimizationSi l d li◦MinCut` Greedy◦Simulated annealing◦ Extremal optimization◦ Bottom up Q` Density◦(α,β)-clustering` Cliques and Bicliques◦ Clique finding` GN betweeness ` DA extremal◦O(n3)` CNM greedyO(nlog2n)◦O(n2log2n)` Modularity matrixO(n2logn)◦O(n log2 n)◦O(n2logn)[Newman 2006][Danon et al 2005][Reichardt, Bornholdt 2006]Community structure in social and biological networks. M Girvan, MEJ Newman - Proceedings of the National Academy of Sciences, 2002. (Cited by 753).Trawling the Web for emerging cyber-communities. R Kumar, P Raghavan, S Rajagopalan, A Tomkins - COMPUT. NETWORKS, 1999. (Cited by 553).Finding and evaluating community structure in networks. MEJ Newman, M Girvan - Physical Review E, 2004. (Cited by 527).Complex networks: Structure and dynamics. S Boccaletti, V Latora, Y Moreno, M Chavez, DU Hwang -Physics Reports 2006 (Cited by 403)-Physics Reports, 2006. (Cited by 403).Uncovering the overlapping community structure of complex networks in nature and society. G Palla, I Derenyi, I Farkas, T Vicsek - Nature, 2005. (Cited by 222).Finding community structure in very large networks. A Clauset, MEJ Newman, C Moore - Physical Review E, 2004. (Cited by 159).fModularity and community structure in networks. MEJ Newman - Proceedings of the National Academy of Sciences, 2006. (Cited by 132).Community detection in complex networks using extremal optimization. J Duch, A Arenas -Physical Review E, 2005. (Cited by 87).Comparing community structure identification.L Danon, A Diaz-Guilera, J Duch, A Arenas-Comparing community structure identification.L Danon, A DiazGuilera, J Duch, A Arenas Journal of Statistical Mechanics: Theory and Experiment, 2005. (Cited by 58).Statistical mechanics of community detection. J Reichardt, S Bornholdt - Physical Review E, 2006. (Cited by 38).Quantifying social group evolution. G Palla, AL Barabasi, T Vicsek - Nature, 2007. (Cited by 29).Fi di C it St t i MlS ilNt kKW kit TT iiFinding Community Structure in Mega-scale Social Networks.K Wakita, T Tsurumi -arxiv.org, 2007. (Cited by 3).Recommending Groups in Social Networks. I Stanton, N Mishra, R. Schreiber, R Tarjan - WWW 2008. (Not yet published). yet published)` “A descriptive task that seeks to identify natural groupings in data.” (Neville et al. 2003)`Partitioning data into nonoverlapping`Partitioning data into non-overlapping groups`Algorithms like k-means and hierarchical`Algorithms like kmeans and hierarchical clustering are used` Data may be drawn from different distributions, and so normal clustering approaches fall short.` Relations between objects may give better insight into clusters` Data instances are not i.i.d. – relations of instances could affect clustering.`Non-relational clustering uses object attributes, but not relations` Relational clustering makes use of connectionsconnections` Neville et al. (2003) showed that using both attributes and links do better than eitherattributes and links do better than either alone (except maybe in some cases where the linkage data is perturbed)` Several examples of specific clustering situations◦ Semi-supervised Clustering◦Co-clustering◦Co-clustering◦ Graph Clustering (Partitioning)` Like unsupervised clustering, but with some pairwise constraints◦ Set M of “must link” constraints (same cluster), and setCof“cannot link”and set Cof cannot linkconstraints (different clusters)◦ Pairwise constraints are moreli ti th ti l t frealistic than a partial set ofclass labels? (Basu et al. 2004)` Many EM approaches[Long et al, 2007]` aka Bi-clustering (Tri-clustering, …)` Have two (or more) types of data, and want to cluster them allP i ll ld`Potentially could useinformation aboutrelationsbetweenrelations betweendata types` Joining nodes/Dividing graph` Approaches mainly consist of edge cut objectivesKMiC t (N ill t l 2003 K 1993)◦Karger Min-Cut (Neville et al. 2003, Karger 1993)◦
View Full Document
Unlocking...