Limits...
Exploring the limits of community detection strategies in complex networks.

Aldecoa R, Marín I - Sci Rep (2013)

Bottom Line: The characterization of network community structure has profound implications in several scientific areas.Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses.We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

View Article: PubMed Central - PubMed

Affiliation: Instituto de Biomedicina de Valencia, Consejo Superior de Investigaciones Científicas, Calle Jaime Roig 11, 46010, Valencia, Spain.

ABSTRACT
The characterization of network community structure has profound implications in several scientific areas. Therefore, testing the algorithms developed to establish the optimal division of a network into communities is a fundamental problem in the field. We performed here a highly detailed evaluation of community detection algorithms, which has two main novelties: 1) using complex closed benchmarks, which provide precise ways to assess whether the solutions generated by the algorithms are optimal; and, 2) A novel type of analysis, based on hierarchically clustering the solutions suggested by multiple community detection algorithms, which allows to easily visualize how different are those solutions. Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses. We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

No MeSH data available.


Related in: MedlinePlus

Best algorithms in RC closed benchmarks.As in Figure 1, this figure shows the six algorithms that recovered the initial partition when C ≥ 5%. SCluster and RNSC showed an excellent behavior, displaying an almost straight blue line, while UVCluster failed in the central, most difficult, part of the benchmark. Infomap and CPM results were somewhat asymmetric, with the latter showing also some degree of instability. RN totally collapses when communities are not well defined.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3713530&req=5

f3: Best algorithms in RC closed benchmarks.As in Figure 1, this figure shows the six algorithms that recovered the initial partition when C ≥ 5%. SCluster and RNSC showed an excellent behavior, displaying an almost straight blue line, while UVCluster failed in the central, most difficult, part of the benchmark. Infomap and CPM results were somewhat asymmetric, with the latter showing also some degree of instability. RN totally collapses when communities are not well defined.

Mentions: The 17 algorithms tested in the LFR and RC closed benchmarks showed very different behaviors, which are summarized in Figures 1,2,3,4. In these figures, following methods developed in previous works45, we show the VI values comparing the partitions obtained by the algorithms with the known initial (red lines) and final (black lines) structures. A perfect agreement with any of these structures corresponds to VI = 0. Also, the value (VIIE + VIEF)/2, (where E is the partition suggested by the algorithm, while I and F are, respectively, the initial and final partitions) is indicated with a blue line. As we discussed before, if the performance of an algorithm is optimal, then, we would expect VIIE + VIEF = VIIF. This means that, in these representations, the blue line should, in the best case, be perfectly straight and located just on top of a thin dotted line also included in these figures, which corresponds to the value VIIF/2.


Exploring the limits of community detection strategies in complex networks.

Aldecoa R, Marín I - Sci Rep (2013)

Best algorithms in RC closed benchmarks.As in Figure 1, this figure shows the six algorithms that recovered the initial partition when C ≥ 5%. SCluster and RNSC showed an excellent behavior, displaying an almost straight blue line, while UVCluster failed in the central, most difficult, part of the benchmark. Infomap and CPM results were somewhat asymmetric, with the latter showing also some degree of instability. RN totally collapses when communities are not well defined.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3713530&req=5

f3: Best algorithms in RC closed benchmarks.As in Figure 1, this figure shows the six algorithms that recovered the initial partition when C ≥ 5%. SCluster and RNSC showed an excellent behavior, displaying an almost straight blue line, while UVCluster failed in the central, most difficult, part of the benchmark. Infomap and CPM results were somewhat asymmetric, with the latter showing also some degree of instability. RN totally collapses when communities are not well defined.
Mentions: The 17 algorithms tested in the LFR and RC closed benchmarks showed very different behaviors, which are summarized in Figures 1,2,3,4. In these figures, following methods developed in previous works45, we show the VI values comparing the partitions obtained by the algorithms with the known initial (red lines) and final (black lines) structures. A perfect agreement with any of these structures corresponds to VI = 0. Also, the value (VIIE + VIEF)/2, (where E is the partition suggested by the algorithm, while I and F are, respectively, the initial and final partitions) is indicated with a blue line. As we discussed before, if the performance of an algorithm is optimal, then, we would expect VIIE + VIEF = VIIF. This means that, in these representations, the blue line should, in the best case, be perfectly straight and located just on top of a thin dotted line also included in these figures, which corresponds to the value VIIF/2.

Bottom Line: The characterization of network community structure has profound implications in several scientific areas.Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses.We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

View Article: PubMed Central - PubMed

Affiliation: Instituto de Biomedicina de Valencia, Consejo Superior de Investigaciones Científicas, Calle Jaime Roig 11, 46010, Valencia, Spain.

ABSTRACT
The characterization of network community structure has profound implications in several scientific areas. Therefore, testing the algorithms developed to establish the optimal division of a network into communities is a fundamental problem in the field. We performed here a highly detailed evaluation of community detection algorithms, which has two main novelties: 1) using complex closed benchmarks, which provide precise ways to assess whether the solutions generated by the algorithms are optimal; and, 2) A novel type of analysis, based on hierarchically clustering the solutions suggested by multiple community detection algorithms, which allows to easily visualize how different are those solutions. Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses. We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.

No MeSH data available.


Related in: MedlinePlus