Detecting Overlapping Communities in Facebook with NodeXL

For the initial public offering of Facebook, I re-publish and extend the main outcomes of this RWTH Aachen  master thesis of my student Arber Ceni  in computer science under my supervision.  Supervision was jointly done with  Marc Smith from Connected Action and  Bernie Hogan from Oxford Internet Institute.

MONC

SPLA

Overlapping vs. Non-overlapping Community Detection

Arber has implemented an importer of Facebook data in NodeXL together with two state-of-the-art algorithms for overlapping community detection, i.e. MONC and SPLA.
The visualization is nicely done. Each node is a pie chart where colors code the percentage of community belonging. You can download and install the importer for free.

Overlapping communities are present in social network sites like Facebook. A Facebook user is on average member of seven communities (paper, slides). Computer scientists and social scientists are interested in analyzing communities. They can detect e.g. formation of trends and voter behavior in the data sets or make use of them for personalized advertisement and stock data. Also for system design data can be used for e.g. system optimization.

Overlapping community detection algorithms (OCDA) are a recent further development of community detection algorithms (CDA). CDA always detect disjoint communities in network data, i.e. each node in the network belongs to exactly one community. A community here is defined sloppily as a more dense sub-network with more intracommunity than intercommunity connections. Because of the fact that in real networks disjoint community membership is extremely rare, OCDA have been proposed.

Some good candidates for OCDA are the following:

K-clique percolation method
+ The first algorithm to detect overlapping communities
+ Yields good results
- Different results for different k
- Doesn't have a good time complexity and fails to analyze large networks

GCE
+ It is fast and accurate
+ Yields the best results on LFR benchmark graphs
+ Able to detect non-overlapping communities
- Needs to specify parameters
- Not good results when nodes don't belong to the same number of communities

MONC
+ Time complexity of only O(n²)
+ Uncovers the whole hierarchical structure of the network in a single run
+ Saves time due to merging of communities
+ The core of the algorithm is free of parameters
- Requires three parameters on the post-processing phase
- The complexity is not proven to be O(n²)

SPLA
+ Has a time complexity of only O(Tn), where T = 100
+ Best results on LFR benchmarks
+ Performs well and is very stable over different ranking criteria
+ Can be easily modified to accommodate different speaker/listener rules
+ Can be used to detect fuzzy and crisp overlapping communities.
- Needs a parameter r