Basis of community Formation The strength of weak ties [Mark Granovetter, 1973] and the models of small-world [Strogatz and Watts, Nature 981 both suggest Strong ties are well embedded in the network Weak ties span long ranges Given a network how do we find all communities?
• The strength of weak ties [Mark Granovetter,1973] and the models of small-world [Strogatz and Watts, Nature’98] both suggest – Strong ties are well embedded in the network – Weak ties span long ranges • Given a network, how do we find all communities? 6 Basis of Community Formation
Community detection Q: Given a network how do we find all communities? A: Find weak ties and identify communities Betweenness centrality [Girvan and Newman, PNAS 02]. Modularity [Newman, PNAS 061 Graph partitioning methods [Karypis and Kumar, SISC08 SFI collaboration network[Newman
• Q: Given a network, how do we find all communities? • A: Find weak ties and identify communities – Betweenness centrality [Girvan and Newman, PNAS’02], – Modularity [Newman, PNAS’06] – Graph partitioning methods [Karypis and Kumar, SISC’08] SFI collaboration network [Newman] 7 Community Detection
[Palla et al. Nature/) Over lapping Communities Communities defined by different nodes in a network may be quite different Scientists Physicists Department of Biological Physics Mathematicians ologists zoom Hobb Scientific Community Family Friends Schoolmates 8
Overlapping Communities • Communities defined by different nodes in a network may be quite different. 8 [Palla et al. Nature’05])
Community search Problem: Given a set of query nodes, find densely connected communities containing them query vertex State-of-the-art research focus Simple and static graphs Evolving, attributed, and oo 8a8 location-based big graphs
Community Search • Problem: Given a set of query nodes, find densely connected communities containing them. • State-of-the-art research focus: Simple and static graphs → Evolving, attributed, and location-based big graphs query vertex 9
Community Detection V.S. Community search Community detection: identify all communities. fundamental widely studied global computation(expensive) static graphs(hard to handle evolving graphs) Community search: find query-dependent communities useful less studied user-centered personalized search dynamIc graphs
Community Detection v.s. Community Search • Community detection: identify all communities. – fundamental & widely studied – global computation (expensive) – static graphs (hard to handle evolving graphs) • Community search: find query-dependent communities – useful & less studied – user-centered& personalized search – dynamic graphs 10