Source-linked AI summary
Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm
Ferran Parés, Dario Garcia-Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguadé, Jesús Labarta, Ulises Cortés, Toyotaro Suzumura
TL;DR
Community detection seeks useful community structure in graphs, but real-world data can support several coherent, unrelated groupings. FluidC uses interacting fluids and propagation, with the number of communities set by initialization. It achieves competitive community quality and scalability while finding communities significantly different from alternatives.
Problem
Real-world graphs may have several coherent but unrelated community structures, so a single detected structure may not capture all useful groupings.
Source: §6 · p. 9Method
FluidC models communities as interacting fluids that expand and push one another through a graph, with the number of communities set by initialization.
Source: §3 · p. 3, §3.1 · p. 4Results
FluidC achieves NMI close to leading alternatives, scales with O(E) computational complexity, and yields communities significantly different from those of other algorithms.
Source: §6 · p. 10, §8 · p. 11Takeaways & Limitations
Alongside Multilevel and Infomap, FluidC may contribute algorithm-independent information when analyzing the same graph.
Source: §6 · p. 10At low mixing parameters (µ ≤0.4), bottleneck edges can prevent proper community flow, leaving NMI slightly sub-optimal at 0.9–0.95.
Source: §4 · p. 7
Abstract
from arXiv · showhide
We introduce a community detection algorithm (Fluid Communities) based on the idea of fluids interacting in an environment, expanding and contracting as a result of that interaction. Fluid Communities is based on the propagation methodology, which represents the state-of-the-art in terms of computational cost and scalability. While being highly efficient, Fluid Communities is able to find communities in synthetic graphs with an accuracy close to the current best alternatives. Additionally, Fluid Communities is the first propagation-based algorithm capable of identifying a variable number of communities in network. To illustrate the relevance of the algorithm, we evaluate the diversity of the communities found by Fluid Communities, and find them to be significantly different from the ones found by alternative methods.
1 Introduction
Community detection extracts a network’s densely connected groups to reveal its organization. FluidC brings propagation’s efficiency to an algorithm that can identify a chosen number of communities.
1 Introduction
- Community detection identifies densely interconnected vertex groups that are sparsely connected to the rest of the graph.This unsupervised analysis can help reveal network organization and characterize the entities in it.Source: §1 · p. 2
- FluidC adapts the efficient propagation methodology used by Label Propagation to model communities as interacting fluids.The fluids expand and push one another through a graph until equilibrium is reached.Source: §1 · p. 2
- By initializing different numbers of fluids, FluidC can find different numbers of communities and examine graph structure at multiple granularities.The paper describes it as the first propagation-based algorithm with this property.Source: §1 · p. 2
2 Related Work
Prior comparisons evaluate community-detection algorithms on synthetic benchmarks and differ in their recommendations. They identify Label Propagation as especially fast and Multilevel as a strong option for community quality.
2 Related Work
- Yang et al. compared eight algorithms using NMI and computing time on LFR graphs, which model scale-free degree and cluster-size distributions.Their study found Multilevel most competitive overall in community-detection quality.Source: §2 · p. 2
- Lancichinetti and Fortunato compared twelve algorithms on GN, LFR, and random graphs, recommending multiple algorithms for algorithm-independent information.They identified Infomap, Multilevel, and Multiresolution [13] as strong candidates.Source: §2 · p. 2
- Both comparisons identify Label Propagation as the fastest algorithm because of propagation’s efficiency and scalability.The studies differ in benchmark scope and in their recommendations for community quality.Source: §2 · p. 2
3 Fluid Communities Algorithm
FluidC models communities as fluids interacting in a non-homogeneous graph and updates vertex memberships using aggregated community density. It also lets users choose the number of communities by initializing different numbers of fluids.
3 Fluid Communities Algorithm
- FluidC initializes k communities at distinct random vertices with inverse-size density, then updates vertices toward communities with maximum aggregated density in their ego networks.Updates run in random-order supersteps until assignments remain unchanged for two consecutive supersteps.Source: §3 · p. 3
- If several communities tie for maximum density, a vertex keeps its current community when it is among the candidates; otherwise, a candidate is sampled uniformly.Updates use the latest partial graph state; a straightforward synchronous version could leave densities inconsistent and allow a community to disappear.Source: §3 · p. 4, §3.1 · p. 4
- FluidC guarantees that no community is eliminated: a community compressed into one vertex has density 1 and remains a candidate for that vertex.Source: §3 · p. 4
3.1 Properties
- Users can set the number of communities by initializing different numbers of fluids, enabling analysis at several levels of granularity; prior methods with this feature were not propagation-based.Source: §3.1 · p. 4
- FluidC avoids monster communities non-parametrically: a large community can maintain or expand its size only with favorable topology that compensates for its lower density.Source: §3.1 · p. 4
- FluidC is designed for connected, undirected, unweighted graphs; disconnected graphs can be handled by running the algorithm independently on each component and appending results.Source: §3.1 · p. 5
4 Evaluation
On LFR benchmark graphs, FluidC’s NMI was competitive with the strongest alternatives overall, with performance depending on graph size and mixing. Its low-mixing results were slightly suboptimal, while its large-graph and high-mixing comparisons favored FluidC over particular alternatives.
4 Evaluation
- The evaluation measured geometric-normalized NMI on LFR graphs spanning six sizes and 25 mixing parameters, with 20 graphs per setting.The resulting 3,000 graphs used the LFR hyperparameters from.Source: §4 · p. 5
- For disconnected LFR graphs, FluidC was run separately on each connected subgraph and the detected communities were combined for overall NMI.Source: §4 · pp. 5–6
- FluidC was competitive with Walktrap and Infomap, close to Multilevel, and beat Walktrap on the largest graph for µ values from 0.33 to 0.66.The largest graph had 22,186 vertices; the reported Walktrap results differ from Yang et al. [16] because of an experimental error acknowledged by those authors.Source: Figure 3 · p. 6, §4 · pp. 6–7
- For comparability, FluidC’s community count k was set to the value yielding the highest modularity, as for Fastgreedy and Walktrap.Source: §4 · p. 6
- FluidC was more resistant to high mixing than Infomap, which could not detect relevant communities for µ > 0.55.Source: §4 · p. 7
- At low mixing (µ ≤0.4), FluidC achieved NMI between 0.9 and 0.95 because bottleneck edges could impede community flow.For real-world graphs described as large and relatively high-mixing, the authors call this sub-optimality a minor inconvenience and recommend LPA for low-mixing graphs.Source: §4 · p. 7
5 Scalability
FluidC’s time per superstep and number of supersteps were similar to LPA’s, yielding analogous linear-time scalability. On larger graphs, FluidC remained close to LPA, while Multilevel was slower and grew faster.
5 Scalability
- FluidC’s time per iteration was virtually identical to LPA’s across graph sizes and mixing parameters, and was almost unaffected by mixing.A superstep checks and updates the communities of all graph vertices.Source: §5 · p. 7
- FluidC and LPA had similar time per superstep and superstep counts, implying analogous computational cost with linear complexity O(E) and scalability.The comparison of convergence counts used FluidC with k set to ground truth; LPA’s results beyond mixing parameter 0.5 were not meaningful because it produced a single community with NMI = 0.0.Source: §5 · p. 7, Figure 4 · p. 8, Figure 5 · p. 8
- On graphs up to 150,000 vertices, LPA was fastest and FluidC followed closely; accounting for LPA’s zero-NMI runs, their scalability was analogous.Source: Figure 4 · p. 8, §5 · p. 8
- Multilevel was 5x slower than LPA/FluidC, with a steeper growth slope of about 10^-5 versus roughly 10^-6 for LPA/FluidC.For PageGraph (3,500M vertices), the estimated processing times were approximately 49 hours for Multilevel and 9 hours for FluidC.Source: §5 · p. 8
6 Diversity of Communities
The section compares six algorithms on 30 graphs with two independent ground truths to assess whether their community-finding behavior differs. FluidC, Infomap, and LPA behave more diversely than the other three algorithms, with FluidC potentially adding a distinct perspective alongside Multilevel and Infomap.
6 Diversity of Communities
- The evaluation uses 30 graphs, each combining two independent ground truths of four communities, generated from graphs with |V| = 22,186 and μ = 0.Minimum and maximum community sizes are 0.2|V| and 0.3|V|; other LFR parameters match the section 4 evaluation.Source: §6 · p. 9
- For each graph, 100 executions yield θ values; a Chi-square test compares algorithms’ categorical distributions, and the 30 similarity matrices are averaged for Figure 6.θ distinguishes preference for either ground truth or equal preference using the difference between their NMI scores and a threshold α; α = 0.5 and α = 0 are reported, and intermediate thresholds produced consistent matrices.Source: §6 · pp. 9–10
- Multilevel, Walktrap, and Fastgreedy have very similar θ values, and their behavioral similarity is stronger at α = 0.The authors note that all three use hierarchical bottom-up agglomeration, while Fastgreedy and Multilevel are modularity-based methods.Source: §6 · p. 10, Figure 6 · p. 10
- FluidC, Infomap, and LPA show behavior patterns significantly different from the other five algorithms, indicating FluidC provides significantly diverse communities.The authors suggest computing FluidC alongside Multilevel and Infomap to contribute algorithm-independent information; all three have competitive LFR performance.Source: §6 · p. 10
7 Reproducibility
The experiments used a specified desktop-class system, and the authors made an open-source FluidC implementation publicly available and integrated it into NetworkX and igraph.
7 Reproducibility
- Experiments ran on OpenSUSE Leap 42.2 (64-bit), an Intel Core i7-5600U CPU at 2.60 GHz, and 16 GB of DDR3 SDRAM.The computer specification describes the experimental environment.Source: §7 · p. 10
- The authors made an open-source FluidC implementation publicly available on GitHub.The implementation was integrated into the NetworkX and igraph graph libraries.Source: §7 · p. 10
- All scalability experiments used the igraph graph library for consistency.The implementation was also integrated into NetworkX.Source: §7 · p. 10
8 Conclusions
FluidC approaches state-of-the-art NMI performance on LFR graphs, with particular competence on large graphs and large mixing parameters, while bottleneck edges limit recovery at small mixing parameters. The authors emphasize its scalability and diversity, including its ability to find variable community counts.
8 Conclusions
- FluidC approaches current best alternatives in LFR NMI, especially on large graphs and at large mixing parameters, but bottleneck edges limit full recovery at small mixing parameters.The authors state that FluidC does not clearly outperform the state of the art in LFR NMI.Source: §8 · p. 11
- FluidC and LPA have linear O(E) complexity, while FluidC produces relevant communities across mixing parameters and Multilevel takes roughly 5× longer to compute.The authors report that Multilevel scales slightly worse and recommend FluidC for graphs of arbitrary large size.Source: §8 · p. 11
- FluidC is the first propagation-based algorithm reported to achieve competitive LFR results and to find a variable number of communities; its communities may differ consistently from those of other algorithms.The authors conclude that community analysis would benefit from including Multilevel, Infomap, and FluidC.Source: §8 · p. 11