We consider the question of finding communities in
social networks. In literature and practice, “communities” refer to a
subgraph of the entire network. For instance, the notion of
has been considered as a reasonable measure of a community. Researchers have also looked at the
of a subgraph as a measure of the connectedness of the community.
Typically, a community is meaningful in the context of a social network if it is of somewhat significant size. Thus, earlier work has considered the densest graph problem subject to various
. Most of these algorithms utilize an exact dense subgraph procedure as a subroutine; such a subroutine involves computing maximum flows or solving LPs. Consequently, they are rather inefficient when considered for massive graphs. For massive graphs, we are constrained to run in near-linear time, while producing subgraphs that provide reasonable approximations to the optimal solutions.
Our current work presents efficient greedy algorithms for the problem of graph density subject to an even more general class of constraints called
constraints (these subsume co-matroid constraints). This generalizes and extends earlier work significantly. For instance, we are thereby able to present near-linear time 3-factor approximation algorithms for density subject to co-matroid constraints; we are also able to obtain 2-factor LP-based algorithms for density subject to 2 co-matroid constraints.
Our algorithms heavily utilize the
of a graph.