An
algorithm to find overlapping community structure in networks
(ECML/PKDD 2007)
We present an algorithm, CONGA, which can detect overlapping communities in
networks. Like the Girvan and Newman algorithm, it uses edge betweenness
to split a network into communities, but it introduces the idea of split
betweenness to split vertices between multiple communities.
More details here.
Local
betweenness for finding communities in networks
The problem with betweenness is that it is very slow to compute. In this paper
we discuss the idea of replacing it by a local form, which counts only "short"
shortest paths rather than all shortest paths. Using local betweenness in the
Girvan and Newman algorithm can reduce its time complexity from O(n3)
to O(n log n). The effectiveness of local betweenness
seems to be determined by the diameter of communities in the network: if communities
have small diameter, it is sufficient to count only short shortest paths.
In the paper we use local betweenness only for detecting disjoint (non-overlapping)
communities. More details here.
A fast
algorithm to find overlapping communities in networks
(ECML/PKDD 2008)
In this paper we present a fast algorithm for finding overlapping communities.
The new algorithm, CONGO, is based on CONGA but uses local betweenness and is
therefore much faster: up to O(m log m) instead of
O(m3). More details here.
Finding
overlapping communities using disjoint community detection algorithms
(CompleNet 2009)
In this paper we present a two-phase method for
finding overlapping communities. The first phase is the new Peacock
algorithm, based on CONGA and CONGO, which transforms a network to an
expanded form. The second phase finds disjoint communities in the transformed
network, using any disjoint clustering algorithm. Finally, the disjoint
communities are postprocessed to form overlapping communities in the original
network. More details here.
Detecting
communities in networks by merging cliques
(ICIS 2009)
(with Bowen Yan)
In this paper we present a new algorithm for finding disjoint communities. The first
phase is to find all cliques using a fast approximate clique-finding algorithm. These
are then merged using a greedy modularity-maximizing algorithm. More
details here.
Finding overlapping communities in
networks by label propagation
(New Journal of Physics)
In this paper we present an algorithm for detecting overlapping communities, based on
label propagation. It generalizes the algorithm by Raghavan et al. that finds disjoint
communities.
More details here.
Fuzzy overlapping
communities in networks
(Journal of Statistical Mechanics:
Theory and Experiment)
In this paper we compare fuzzy and crisp overlapping of communities in networks.
We look at the effect this has on community detection algorithms, and consider algorithms
that can recover the fuzzy belonging coefficients.
More details here.
Ordered community structure in networks
(Physica A: Statistical Mechanics and its Applications)
Community structure in networks is often caused by homophily, or assortative mixing,
based on some discrete attribute of the vertices. In this paper we consider how
community structure can be generalized to networks whose vertex attributes are ordered
(discrete or continuous) values, such as age or geographical location. In particular,
we show that current community detection algorithms fail to work for ordered networks,
and propose an alternative method using a layout algorithm to recover the ordering.
More details here.