 |
Center for Nonlinear Studies |
Many systems, from the living cell and the Internet to the brain and human society, can be modeled using networks that possess communities, small groups of densely interconnected --- and often overlapping --- nodes. We provide an overview of the community detection problem and introduce new results describing how some of the most basic assumptions about these structures may not hold. Meanwhile, the robustness of these systems to breakdown can be studied using percolation: a random fraction of the nodes fail which may cause the network to lose global connectivity. We show analytically that the communities themselves can become isolated or non-overlapping well before the network falls apart, indicating that networks undergo additional structural transitions above the typical percolation threshold. Finally, we present a new type of community discovery algorithm that outperforms many of the most cutting edge methods currently available.
Host: Aric Hagberg, T-5, hagberg@lanl.gov