Fuzzy communities and the concept of bridgeness in complex networks

Abstract

We consider the problem of fuzzy community detection in networks, which complements and expands the concept of overlapping community structure. Our approach allows each vertex of the graph to belong to multiple communities at the same time, determined by exact numerical membership degrees, even in the presence of uncertainty in the data being analyzed. We created an algorithm for determining the optimal membership degrees with respect to a given goal function. Based on the membership degrees, we introduce a new measure that is able to identify outlier vertices that do not belong to any of the communities, bridge vertices that belong significantly to more than one single community, and regular vertices that fundamentally restrict their interactions within their own community, while also being able to quantify the centrality of a vertex with respect to its dominant community. The method can also be used for prediction in case of uncertainty in the dataset analyzed. The number of communities can be given in advance, or determined by the algorithm itself using a fuzzified variant of the modularity function. The technique is able to discover the fuzzy community structure of different real world networks including, but not limited to social networks, scientific collaboration networks and cortical networks with high confidence.

13 pages, 9 figures. Quality of Fig. 4 reduced due to file size considerations

References in corpus (7)

• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Comparing community structure identification
• Vertex similarity in networks

Cited by in corpus (60)

• Community detection in graphs
• Community detection algorithms: a comparative analysis
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Controlling edge dynamics in complex networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Fuzzy overlapping communities in networks
• Lobby index in networks
• Overlapping Community Detection in Complex Networks using Symmetric Binary Matrix Factorization
• Modularity measure of networks with overlapping communities
• SLPA: Uncovering Overlapping Communities in Social Networks via A Speaker-listener Interaction Dynamic Process
• Map equation for link community
• A New Approach to Analyzing Patterns of Collaboration in Co-authorship Networks - Mesoscopic Analysis and Interpretation
• backbone: An R package to extract network backbones
• Drug-therapy networks and the predictions of novel drug targets
• Detecting global bridges in networks
• Followers Are Not Enough: A Question-Oriented Approach to Community Detection in Online Social Networks
• Detection of node group membership in networks with group overlap
• Stochastic block model and exploratory analysis in signed networks
• GenPerm: A Unified Method for Detecting Non-overlapping and Overlapping Communities
• Bridges in Complex Networks
• Overlapping community detection in signed networks
• Extension of Modularity Density for Overlapping Community Structure
• An Enhanced Multi-Objective Biogeography-Based Optimization for Overlapping Community Detection in Social Networks with Node Attributes
• Walk modularity and community structure in networks
• Fast Detection of Community Structures using Graph Traversal in Social Networks
• Co-community Structure in Time-varying Networks
• A framework for second order eigenvector centralities and clustering coefficients
• Improvements on SCORE, Especially for Weak Signals
• Network cross-validation by edge sampling
• A similarity-based community detection method with multiple prototype representation
• Community detection by spectral methods in multi-layer networks
• Fuzzy Overlapping Community Quality Metrics
• Finding overlapping communities in multiplex networks
• Egomunities, Exploring Socially Cohesive Person-based Communities
• Centrality properties of directed module members in social networks
• Overlapping modularity at the critical point of k-clique percolation
• Growing networks of overlapping communities with internal structure
• Analytical Formulation of the Block-Constrained Configuration Model
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Online Tensor Methods for Learning Latent Variable Models
• Evidential Communities for Complex Networks
• Criterions for locally dense subgraphs
• Finding mixed memberships in categorical data
• Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
• The Atlas for the Aspiring Network Scientist
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• Dual regularized Laplacian spectral clustering methods on community detection
• Metrics for Community Analysis: A Survey
• Ensemble-Based Discovery of Disjoint, Overlapping and Fuzzy Community Structures in Networks
• An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
• Mixed membership estimation for categorical data with weighted responses
• Mixed-SCORE+ for mixed membership community detection
• Searching for network modules
• Overlapping community detection in weighted networks
• Understanding Vulnerability of Communities in Complex Networks