Extending the definition of modularity to directed graphs with overlapping communities

Abstract

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.

22 pages, 11 figures

References in corpus (19)

• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in complex networks using Extremal Optimization
• Why social networks are different from other types of networks
• Community structure in directed networks
• Module identification in bipartite and directed networks
• Size reduction of complex networks preserving modularity
• The origin of degree correlations in the Internet and other networks
• Directed network modules
• Network dynamics of ongoing social relationships
• Correlations in Scale-Free Networks: Tomography and Percolation

Cited by in corpus (28)

• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Finding overlapping communities in networks by label propagation
• Line Graphs, Link Partitions and Overlapping Communities
• Clustering and Community Detection in Directed Networks: A Survey
• Uncovering space-independent communities in spatial networks
• A Classification for Community Discovery Methods in Complex Networks
• Graph Metrics for Temporal Networks
• Identifying the Community Structure of the International-Trade Multi Network
• Clique Graphs and Overlapping Communities
• Line Graphs of Weighted Networks for Overlapping Communities
• Fuzzy overlapping communities in networks
• Quantifying and identifying the overlapping community structure in networks
• Directed clustering in weighted networks: a new perspective
• Modularity measure of networks with overlapping communities
• Classifying Patents Based on their Semantic Content
• Detecting Communities in Networks by Merging Cliques
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Extension of Modularity Density for Overlapping Community Structure
• Combinatorial approach to Modularity
• Walk modularity and community structure in networks
• Fast Detection of Community Structures using Graph Traversal in Social Networks
• Fuzzy Overlapping Community Quality Metrics
• Community detection and reciprocity in networks by jointly modeling pairs of edges
• Overlapping modularity at the critical point of k-clique percolation
• Wall-induced anisotropy effects on turbulent mixing in channel flow: A network-based analysis
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• Clubmark: a Parallel Isolation Framework for Benchmarking and Profiling Clustering Algorithms on NUMA Architectures
• Ranking of Communities in Multiplex Spatiotemporal Models of Brain Dynamics