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)
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
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.