Title: Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach
Speaker: Rong Ge, Princeton University
Date: Wednesday, September 14, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A community in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. Many existing methods for finding them use heuristic algorithms where the solution concept is defined in terms of an NP-complete problem such as CLIQUE or HIERARCHICAL CLUSTERING.
We introduce a more formal approach whereby we make rigorous definitions that sidestep the pitfall of high computational complexity and allow efficient algorithms for finding communities. Our definition includes as subcases more traditional definitions of communities including clique and dense subgraph. The hallmark of our approach is that it allows each node to belong to more than one community, which had seemed problematic in earlier approaches that view communities as nonexpanding sets.
The ability to sidestep computational complexity arises from making "common sense" assumptions about the network that are between worst-case and average-case assumptions. A key tool in our algorithms is use of random sampling similar to that in property testing and algorithms for dense graphs. We note however that our networks are not necessarily dense graphs, not even in local neighborhoods.
Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work.