Generalized communities in networks

Posted on by Brandon Klein

A substantial volume of research has been devoted to studies
of community structure in networks,
but communities are not the only possible form of large-scal
e network structure. Here we describe
a broad extension of community structure that encompasses t
raditional communities but includes a
wide range of generalized structural patterns as well. We de
scribe a principled method for detecting
this generalized structure in empirical network data and de
monstrate with real-world examples how
it can be used to learn new things about the shape and meaning o
f networks.
The detection and analysis of large-scale structure in
networks has been the subject of a vigorous research
effort in recent years, in part because of the highly
successful application of ideas drawn from statistical
physics [1, 2].  Particular energy has been devoted to
the study of community structure, meaning the division
of networks into densely connected subgroups, a common
and revealing feature, especially in social and biological
networks [3]. Community structure is, however, only one
of many possibilities where real-world networks are con-
cerned.  In this paper, we describe a broad generaliza-
tion of community structure that encompasses not only
traditional communities but also overlapping or fuzzy
communities, ranking or stratified structure, geometric
networks, and a range of other structural types, yet is
easily and flexibly detected using a fast, mathematically
principled procedure which we describe. We give demon-
strative applications of our approach to both computer-
generated test networks and real-world examples.
Community structure can be thought of as a division
of the nodes of a network into disjoint groups such that
the probability of an edge is higher between nodes in
the same group than between nodes in different groups.
For instance, one can generate artificial networks with
community structure using the stochastic block model, a
mathematical model that follows exactly this principle.
In the stochastic block model the nodes of a network...