Source-linked AI summary
Extending the definition of modularity to directed graphs with overlapping communities
V. Nicosia, G. Mangioni, V. Carchiolo, M. Malgeri
TL;DR
The paper addresses the limitation that Newman’s modularity sharply separates communities and cannot represent overlaps. It extends modularity to directed graphs with overlapping communities and presents a genetic-algorithm method for optimizing the extension, with applications to benchmark case studies.
Problem
Newman’s modularity does not account for possible overlaps among communities, despite overlapping structures occurring in complex networks.
Method
The paper generalizes modularity using an enriched null model and proposes genetic-algorithm optimization for discovering overlapping communities.
Results
The proposed extension yields higher modularity values for strong overlapping community structures and is applied to benchmark case studies.
Takeaways & Limitations
Directed networks with overlapping communities can be evaluated and analyzed by extending modularity and optimizing it for community discovery.
Takeaways & Limitations
The edge-contribution function remains unspecified for future research, while genetic-algorithm optimization can stall at local maxima and find non-optimal solutions.
Abstract
from arXiv · showhide
Complex networks topologies present interesting and surprising properties, such as community structures, which can be exploited to optimize communication, to find new efficient and context-aware routing algorithms or simply to understand the dynamics and meaning of relationships among nodes. Complex networks are gaining more and more importance as a reference model and are a powerful interpretation tool for many different kinds of natural, biological and social networks, where directed relationships and contextual belonging of nodes to many different communities is a matter of fact. This paper starts from the definition of modularity function, given by M. Newman to evaluate the goodness of network community decompositions, and extends it to the more general case of directed graphs with overlapping community structures. Interesting properties of the proposed extension are discussed, a method for finding overlapping communities is proposed and results of its application to benchmark case-studies are reported. We also propose a new dataset which could be used as a reference benchmark for overlapping community structures identification.
1. Introduction
Graph partitioning supports application-specific goals, but real networks often contain communities with overlapping membership that conventional clustering and modularity-based methods do not represent.
- Graph partitioning is used to optimize bandwidth or minimize communication flow, depending on the application.
- Communities are valuable because they combine dense internal connectivity, short paths, and robustness.
- Classical clustering methods focus on structural subdivisions and therefore do not adequately reveal community link patterns and relationships.
- Modularity is a widely used metric for evaluating community structure and has been extended from undirected to directed networks.
- Modularity optimization traditionally produces binary vertex partitions, preventing the discovery of partially overlapping communities.
- The paper extends modularity to directed graphs with overlapping communities and applies a genetic-algorithm optimization method.
2. Newman’s Modularity
Newman’s modularity compares observed within-community links with expectations from a degree-preserving random null model, with directed versions distinguishing link direction. Its key limitation is enforcing non-overlapping vertex communities.
- Newman’s modularity treats a subgraph as a community when its internal links exceed those expected in a comparable random graph.
- The null model preserves node and edge counts and degree distributions while randomly placing links.
- For a candidate community, modularity sums differences between actual and null-model expected links among its vertices.
- The directed extension uses a directed null model, so Pij and Pji represent probabilities for opposite link directions.
- The formulation has been used successfully to identify or confirm communities in several relatively large networks.
- Its central limitation is that each vertex belongs to only one community, ruling out overlapping community structures.
3. Modularity for directed graphs with overlapping communities
The paper generalizes modularity to directed graphs whose nodes can have graded membership in multiple communities. It uses a degree-preserving, membership-independent null model and weights edge contributions by endpoint belonging factors.
- The proposed metric targets smooth community structures in directed graphs with overlapping memberships.
- Each node receives a belonging factor for every community, expressing the strength of its membership.
- Edge belonging is represented by a function of the endpoint belonging factors, but the paper leaves the function’s precise form open.
- The generalized modularity weights both observed adjacency entries and null-model probabilities by shared community belonging.
- The null model preserves every node’s in-degree and out-degree while making community memberships of different nodes independent.
- Qov satisfies zero modularity for a single-community assignment and increases with stronger overlapping community structure.
4. Modularity optimization as a genetic problem
The paper maps overlapping-community modularity optimization onto a genetic algorithm whose chromosomes encode node–community belonging strengths. The algorithm evolves normalized populations through fitness evaluation and genetic operators, with ncomm constraining the searched solution space.
- Genetic formulation: Genetic algorithms search large optimization spaces by evolving populations of chromosome-encoded candidate solutions.Higher-fitness individuals are selected for subsequent generations, while crossover and mutation create new candidates.
- Genetic formulation: QOV serves as the fitness function, and candidate solutions are graph partitions into overlapping communities.Higher QOV values correspond to better graph decompositions.
- Chromosome representation: Each chromosome is a matrix M = (α_i,c), where α_i,c ∈ [0.0, 1.0] represents node i’s belonging strength to community c.The representation is illustrated in Figure 1.
- Chromosome representation: Node belonging factors are normalized to prevent solutions assigning unity membership to several communities simultaneously.The constraint favors solutions where a node with belonging factor 1.0 belongs to only one community.
- Algorithm: The algorithm iterates genetic operations over a population initialized with random, normalized belonging factors.Inputs include epochs, population size, and the optional maximum number of overlapping communities, ncomm.
Fitness evaluation, sorting and selection.
Fitness evaluation computes modularity for each chromosome, after which high-fitness individuals are retained and replaced or supplemented by newly generated members.
- Fitness evaluation: Fitness evaluation calculates the modularity function for every individual chromosome.Selected high-fitness individuals continue into the next generation.
- Sorting and selection: New population members are generated through crossover among better individuals or created from scratch.
Crossover and Mutation.
The genetic operators combine and perturb chromosome values to generate new candidate solutions. Crossover copies one community column in one direction, while mutation randomly changes a node’s community belonging factor.
- Crossover: Crossover exchanges chromosome information to create offspring from two population members.
- Crossover: Figure 2 presents the crossover operation used by the genetic algorithm.
- Crossover: The implemented crossover chooses a random community column and copies it from chromosome CA into CB.The operation is one-way: CB changes while CA remains unchanged.
- Mutation: Mutation randomly selects individuals, nodes, and communities before changing a node’s belonging factor.
Clean–up.
The CleanUp function adjusts node–community belonging factors using neighboring nodes’ average memberships. The authors report improvements in both partition quality and genetic-algorithm convergence speed.
- CleanUp mechanism: CleanUp evaluates neighboring nodes’ average belonging to a selected community for a randomly chosen node and community.It also evaluates the corresponding average for nodes that are not neighbors.
- CleanUp mechanism: If neighbors have the higher average belonging, CleanUp increases the selected node’s belonging factor; otherwise, it decreases it.This uses local link-pattern information to guide the solution toward a meaningful optimum.
- Reported effect: The CleanUp function significantly improves community-partition quality and genetic-algorithm convergence speed.
- Normalization: Normalization follows crossover, mutation, and CleanUp because those operations can violate the chromosome constraint.
Computational complexity of the algorithm.
The proposed algorithm’s worst-case complexity is determined by fitness evaluation and scales with the number of communities and nodes.
- O(|C| *n2) is the proposed algorithm’s worst-case complexity.The critical operation is fitness evaluation, where n is the number of network nodes and |C| is the number of communities.
5. Results
The generalized modularity and genetic-algorithm optimization recover overlapping and hierarchical community structures across several benchmark and applied networks. Results include meaningful overlaps in the Karate Club, dolphins, PolBooks, and engineering-student networks, while the student network is proposed as a future benchmark.
- Networks evaluated: The experiments maximize generalized modularity on the Zachary Karate Club, dolphins, PolBooks, and engineering-student networks.The first two are established community-detection benchmarks; PolBooks links books purchased together and includes political-party labels.
- The Zachary Karate Club: A two-community Karate Club solution assigns partial memberships to nodes 3 and 10, identifying overlap between the main communities.The reported coefficients are α3,0 = 0.81 and α10,0 = 0.63, while other nodes receive binary assignments for the relevant community.
- The Zachary Karate Club: The optimal Karate Club solution appears in 98% of genetic-algorithm runs, while near-equivalent local maxima reveal additional border-node overlaps.The sub-optimal solution retains the overlaps of nodes 3 and 10 and adds nodes 9, 31, and 34, which connect to the first community.
- The Zachary Karate Club: The generalized modularity formulation captures overlaps and, to some extent, hierarchical community organization in the Karate Club network.With up to ten communities allowed, the algorithm leaves six empty and finds four nonempty communities, including the two original communities and their overlaps.
- The social network of dolphins: The dolphins results recover four communities and slight overlaps between sub-communities within each major community.Examples include overlap between the small red male sub-community and the blue community, and between the green female sub-community and its neighboring community.
- The PolBooks network: In PolBooks, neutral books are placed between overlapped conservative and liberal communities, unlike common two- or four-community partitions.A small number of liberal books also overlap with the conservative community.
- Students in computer engineering: The engineering-student network has about sixty nodes and more than one hundred and fifty links, with roughly one-third of nodes overlapped between two communities.It is described as well connected with a very low average path length, although the cause of the massive overlap was not clearly explained.
- Students in computer engineering: The engineering-student network is proposed as a future reference benchmark for testing overlapping-community detection algorithms.
6. Conclusions
The paper extends modularity to directed graphs with overlapping communities and proposes a genetic-algorithm method to optimize the extended function. It applies the proposal to several complex networks.
- The paper extends modularity to directed graphs with overlapping communities using an enriched null model.The null model accounts for nodes belonging to more than one community simultaneously.
- A genetic algorithm is presented to discover overlapping communities by optimizing the extended modularity function.
- The paper reports applications of the proposal to several complex networks.