On Accuracy of Community Structure Discovery Algorithms

Home ▸ Literature Survey ▸ On Accuracy of Community Structure Discovery Algorithms

---

Year: 2011
Authors: Günce Keziban Orman, Vincent Labatut, Hocine Cherifi
File: orman_2011.pdf

---

Contents

• 1. Community Detection Algorithms
  • 1.1 Link-Centrality-Based Algorithms
  • 1.2 Modularity Optimization Algorithms
  • 1.3 Spectral Algorithms
  • 1.4 Random-Walk-Based Algorithms
  • 1.5 Information-Based Algorithms
  • 1.6 Other Algorithms
• 2. Method
  • 2.1 Artificial Network Generation
  • 2.2 Performance Assessment
• 3. Results

Community Detection Algorithms

Link-Centrality-Based Algorithms

• Radetal (Radicchi et al.)

Back to Top

---

Modularity Optimization Algorithms

• FastGreedy (FG) (Newman et al.)
• Louvain (LV) (Blondel et al.)
• Spinglass (SG) (Reichardt and Bornholdt)

Back to Top

---

Spectral Algorithms

• Leading Eigenvector (LEV) (Newman)
• Commfind (CF) (Donetti and Muñoz)

Back to Top

---

Random-Walk-Based Algorithms

• Walktrap (WT) (Pons and Latapy)
• MarkovCluster (MCL)

Back to Top

---

Information-Based Algorithms

• Infomod (IND) (Rosvall and Bergstorm)
• Infomap (INP) (Rosvall and Bergstorm)

Back to Top

---

Other Algorithms

• Label Propagation (LP) (Raghavan et al.)

Back to Top

Method

Artificial Network Generation

• generated benchmark graph using the LFR benchmark;
  • nodes degrees and community sizes are both power-law distributed;

Back to Top

---

Performance Assessment

• as artificial networks are used, their communities are known a priori;
• uses NMI (Normalized mutual information) to compare algorithms;
  • NMI ranges from 0 to 1;
  • If the estimated communities correspond perfectly to the actual ones, the measure takes the value 1;
  • It is zero when the estimated communities are independent from the actual ones;
• for each combination of parameters, a sample containing 25 networks was produced;
• each of the eleven community detection algorithms presented are tested on all generated samples;
• their partitioning performance is assessed using NMI;
• to compare the algorithms, we average the measured NMI values over the 25 networks of each sample;
• to assess their influence, we calculate Pearson’s correlation between each parameter and the NMI values;

Back to Top

Results

• In all cases Infomap outperforms all the other algorithms under investigation. It succeeds in identifying the communities even for high mixing coefficient values.
• Walktrap, MarkovCluster, SpinGlass and Louvain also have an excellent performance level, although not as good.
• Leading Eigenvector and Commfind are clearly outclassed.
• Label Propagation exhibits very different results for sample networks generated with the same parameters values.
• The network size and the average degree are two other parameters which influence algorithms performance.
• When the network size increases, some algorithms (Infomap, Infomod, Louvain) perform better, some others perform worse (Commfind, SpinGlass, LeadingEigenvector, Louvain, Radetal) and for the rest of the algorithms (Walktrap, FastGreedy, MarkovCluster), the performances does not change.
• For all algorithms, the higher the degree, the better the performance.

Back to Top