Community Finding Algorithms

Machine Learning Group University College Dublin Community Finding Algorithms Pádraig Cunningham Konstanz June Centrality the nodes that are central and pivotal for communication. Communities the communities that exist Flow the way information and influence flows Anomalous Structure the remarkable or anomalous structure that exists Research Issues in SNA 2 (Greene et al. ECCBR 2008) Konstanz June Outline Established Techniques Spectral Clustering Girvan Newman Algorithm CFinder Further Challenges Overlapping Communities Multi-relation Networks Scale Recent Progress CONGA PICA Scalability through Problem Decomposition 3 Konstanz June Outline Established Techniques Spectral Clustering Girvan Newman Algorithm CFinder Further Challenges Overlapping Communities Multi-relation Networks Scale Recent Progress CONGA PICA Scalability through Problem Decomposition 4 Konstanz June A B C D E G H J F 5

Spectral Clustering What are the natural groups in this graph? Konstanz June A B C D E G H J F (Normalised) Minimum Cut 5 Spectral Clustering What are the natural groups in this graph? Konstanz June A B C D E G H J T = [ 1,1,0,1,1,0,0,0,0; 1,1,1,1,1,0,0,0,0; 0,1,1,1,0,0,0,0,0; 1,1,1,1,1,0,0,0,0; 1,1,0,1,1,1,1,0,0; 0,0,0,0,1,1,1,1,0; 0,0,0,0,1,1,1,1,1; 0,0,0,0,0,1,1,1,1; 0,0,0,0,0,0,1,1,1; ]F (Normalised) Minimum Cut 5 Spectral Clustering What are the natural groups in this graph? Konstanz June A B C D E G H J T = [ 1,1,0,1,1,0,0,0,0; 1,1,1,1,1,0,0,0,0; 0,1,1,1,0,0,0,0,0; 1,1,1,1,1,0,0,0,0; 1,1,0,1,1,1,1,0,0; 0,0,0,0,1,1,1,1,0; 0,0,0,0,1,1,1,1,1; 0,0,0,0,0,1,1,1,1; 0,0,0,0,0,0,1,1,1; ]F (Normalised) Minimum Cut 5 Spectral Clustering What are the natural groups in this graph? DG = sum(T) D = diag(DG) L = D-T [V,S] = eig(L) Konstanz June 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 T 4 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 3 D (Degree Matrix) 3 -1 0 -1 -1 0 0 0 0 -1 4 -1 -1 -1 0 0 0 0 0 -1 2 -1 0 0 0 0 0 -1 -1 -1 4 -1 0 0 0 0 -1 -1 0 -1 5 -1 -1 0 0 0 0 0 0 -1 3 -1 -1 0 0 0 0 0 -1 -1 4 -1 -1 0 0 0 0 0 -1 -1 3 -1 0 0 0 0 0 0 -1 -1 2 L The eigen-decomposition of the Laplacian of the link matrix reveals the cluster structure L = D - T Spectral Clustering 6 Konstanz June 0 0 0 0 0 0...

Website: www.csi.ucd.ie | Filesize: -
No of Page(s): 65
Download Community Finding Algorithms - University College Dublin.pdf