Source-linked AI summary
DEMON: a Local-First Discovery Method for Overlapping Communities
Michele Coscia, Giulio Rossetti, Fosca Giannotti, Dino Pedreschi
TL;DR
Large networks may not exhibit a clear global community organization, limiting traditional top-down discovery of latent modular knowledge. DEMON instead has nodes vote on communities in their local ego neighborhoods, merges those views globally, and reports strong real-world predictive quality alongside deterministic, incremental, and low-complexity properties.
Problem
Community discovery in large complex networks lacks a clear global organization, while traditional graph partitioning imposes a top-down global view that can miss latent modular knowledge.
Method
DEMON applies label propagation to each node’s ego-minus-ego network and democratically merges the resulting local communities into an overlapping global collection.
Results
DEMON clearly outperforms selected overlapping and non-overlapping methods in community quality evaluated through metadata prediction on several real-world networks.
Takeaways & Limitations
Its determinacy, incrementality, and low theoretical linear time complexity make DEMON suitable for analyzing networks with millions of nodes.
Takeaways & Limitations
An efficient parallel implementation and alternative merging strategies remain open directions for improving DEMON’s scalability and results.
Abstract
from arXiv · showhide
Community discovery in complex networks is an interesting problem with a number of applications, especially in the knowledge extraction task in social and information networks. However, many large networks often lack a particular community organization at a global level. In these cases, traditional graph partitioning algorithms fail to let the latent knowledge embedded in modular structure emerge, because they impose a top-down global view of a network. We propose here a simple local-first approach to community discovery, able to unveil the modular organization of real complex networks. This is achieved by democratically letting each node vote for the communities it sees surrounding it in its limited view of the global system, i.e. its ego neighborhood, using a label propagation algorithm; finally, the local communities are merged into a global collection. We tested this intuition against the state-of-the-art overlapping and non-overlapping community discovery methods, and found that our new method clearly outperforms the others in the quality of the obtained communities, evaluated by using the extracted communities to predict the metadata about the nodes of several real world networks. We also show how our method is deterministic, fully incremental, and has a limited time complexity, so that it can be used on web-scale real networks.
1. INTRODUCTION
DEMON addresses the difficulty of discovering communities in large networks by replacing global partitioning with local perspectives that are merged into an overlapping global structure. The method is evaluated on real-world networks through metadata prediction and is designed for scalable, evolving graphs.
- Large networks can lack a clear global modular organization, making traditional top-down community discovery difficult.Even a 15,000-node fragment of Facebook’s much larger friendship graph is difficult to interpret globally.
- Local ego neighborhoods expose cohesive groups that are difficult to identify in the full network.Removing an ego node from its ego network can reveal groups such as school, university, workplace, and online-community connections.
- The local-first approach is motivated by applying community definitions at small scales, where modular structure is more readily visible.The paper contrasts this with methods that optimize a global quality function over the entire network.
- DEMON lets each node identify communities in its ego-minus-ego network using label propagation, then merges these local views into overlapping global modules.The ego is judged by its neighbors, and the resulting perspectives are combined democratically.
- DEMON is evaluated against overlapping and non-overlapping state-of-the-art methods using extracted communities to predict node metadata in Amazon, IMDb, and GovTrack.us.The evaluation focuses on the useful knowledge recovered from communities.
2. RELATED WORK
Prior community-discovery work includes modularity optimization, information-theoretic methods, overlapping-community algorithms, and label propagation. These approaches differ in objectives, scalability, and whether they produce overlapping or global community structures.
- Traditional community discovery commonly models communities as dense subgraphs with relatively few outgoing edges.The paper notes that this definition does not cover many real-world cases.
- Modularity-based methods optimize a partition quality function that favors higher internal than external cluster density.The literature includes extensive work on maximizing modularity and analyzing its deficiencies.
- Infomap is selected as a non-overlapping baseline because it is reported among the best-performing non-overlapping algorithms.The paper contrasts information-theoretic methods with modularity approaches.
- Overlapping methods allow nodes to belong to multiple communities, reflecting memberships such as family, work, and hobbies.Examples include Hierarchical Link Clustering, HCDF, and k-clique percolation.
- Label Propagation spreads labels through graph edges and groups nodes sharing labels, offering quasi-linear speed but ordinarily no overlapping partition.The paper states that plain label propagation performs worse than Infomap in results.
- A related local-community method does not return a global modular organization, while other network-analysis work targets influence and viral-marketing applications.These works address adjacent goals rather than DEMON’s local-to-global construction.
3. NETWORKS AND COMMUNITIES
The paper formalizes networks as graphs and defines communities through ego-minus-ego neighborhoods. Global communities are obtained by selecting maximal local communities across all nodes, and DEMON operationalizes this process algorithmically.
- Networks are represented as undirected, unlabeled, unweighted simple graphs G = (V, E), although the method can handle weighted, directed, labeled multigraphs.Nodes are vertices and links are edges connecting pairs of vertices.
- Community discovery is narrowed from the ambiguous general goal of finding communities to a specific graph-based community definition.The paper emphasizes that community has no unique meaning in complex, semantically rich networks.
- For each node, EgoMinusEgo removes the node and its attached edges from its ego network, and local communities are possibly overlapping similar-node sets within that structure.Each local set groups nodes that are more similar to one another than to nodes in other local communities.
- Global communities are the maximal local communities collected from the EgoMinusEgo network of every node.Maximal means no selected set is strictly contained in another set.
- Algorithm 1 processes every node, applies LabelPropagation to its ego-minus-ego graph, adds the ego to each local community, merges communities, and returns an overlapping set.The procedure initializes an empty community collection and uses a merge parameter ϵ.
4. THE ALGORITHM
DEMON discovers overlapping communities locally by applying Label Propagation to each node’s EgoMinusEgo network, then merging the resulting local communities. Its maximal-set formulation supports correctness, order-insensitivity, compositionality, incrementality, and network-scale execution under stated conditions.
- Core algorithm: DEMON applies Label Propagation separately to each node’s EgoMinusEgo network, then reintroduces the node into its locally discovered communities.EgoMinusEgo removes the focal node and its attached edges before local discovery, avoiding noise from its direct links to neighbors.
- Core algorithm: Label Propagation assigns nodes the most frequent neighbor label, groups equal-label nodes into communities, and can identify overlaps when multiple labels tie.The process initializes unique labels, iterates through nodes in an order, and stops at consensus or tmax iterations.
- Merge function: DEMON merges local communities when at most ε% of the smaller community is absent from the larger, replacing them with their union.At ε = 0, merging requires a proper-subset relationship; at ε = 1, even disjoint communities may merge.
- Correctness: The algorithm retains maximal local communities as nodes are processed, yielding all and only communities obtained by extending the initial set with communities found in the graph.This follows from the maximal-set operation and the merge invariant maintained across the outer loop.
- Properties: DEMON’s output is independent of node-visit order, provided each node’s local communities are uniquely assigned.The property follows from the uniqueness of the maximal-set collection operation.
- Properties: DEMON is compositional and incremental under stated ego-network conditions, allowing independent processing of graph fragments and reanalysis only around newly affected nodes.Its core is therefore parallelizable, while updates can be processed without rerunning the algorithm on the entire expanded graph.
- Complexity: O(nK3−α) complexity results for a scale-free network with degree exponent α and maximum degree K; α = 2 remains subquadratic because K << n.The analysis attributes lower complexity to stronger α, while α = 2 produces higher but still subquadratic complexity.
5. EXPERIMENTS
DEMON is evaluated on three real-world networks using label prediction and community cohesion, with comparisons to overlapping and non-overlapping methods. The experiments report strong quality, manageable community counts, and practical examples of overlapping product communities.
- Experimental design: The evaluation uses three real-world networks and compares DEMON with overlapping and non-overlapping community discovery methods.The assessment focuses on predictive power from discovered communities and global semantic cohesion.
- Label prediction: DEMON outperforms its competitors on F-Measure for the Congress and IMDb datasets.Amazon is excluded from analytic evaluation because HLC failed due to complexity and other methods produced communities that were difficult to analyze.
- Label prediction: For IMDb, DEMON achieves similar quality to HLC with 70-80% fewer communities and more manageable average community size than Infomap.The comparison uses the communities returned by DEMON with ϵ = 0.
- Community size: Infomap returns an Amazon community one order of magnitude larger than DEMON’s largest community, making it impossible to analyze.This community-size imbalance prevents an analytical evaluation of Amazon results.
- Qualitative analysis: Amazon communities can distinguish different product-interest groups around the same item, supporting recommendation-oriented knowledge extraction.The Guns, Germs, and Steel example contains two distinct, overlapping communities with different product characteristics.
6. CONCLUSION AND FUTURE WORKS
DEMON uses a democratic local approach to detect overlapping communities and reports improved partition quality on real-world networks. Its theoretical properties support analysis of networks with millions of nodes, while billion-node scaling and alternative design choices remain future work.
- Conclusion: DEMON lets peer nodes judge where their neighbors should be clustered, producing overlapping communities from local information.The method combines local judgments into a global collection of modules.
- Conclusion: DEMON's correctness, completeness, determinacy, compositionality, and incrementality make it suitable for analyzing networks with millions of nodes.
- Conclusion: The experiments report improved overlapping-partition quality over state-of-the-art algorithms using metadata prediction and a metadata-based quantitative quality function.
- Future work: Future work includes parallelization for billion-node networks, alternative merging strategies, and replacing Label Propagation with algorithms based on different community definitions.