Partition of Networks into Basins of Attraction

Abstract

We study partition of networks into basins of attraction based on a steepest ascent search for the node of highest degree. Each node is associated with, or "attracted" to its neighbor of maximal degree, as long as the degree is increasing. A node that has no neighbors of higher degree is a peak, attracting all the nodes in its basin. Maximally random scale-free networks exhibit different behavior based on their degree distribution exponent $\gamma$: for small $\gamma$ (broad distribution) networks are dominated by a giant basin, whereas for large $\gamma$ (narrow distribution) there are numerous basins, with peaks attracting mainly their nearest neighbors. We derive expressions for the first two moments of the number of basins. We also obtain the complete distribution of basin sizes for a class of hierarchical deterministic scale-free networks that resemble random nets. Finally, we generalize the problem to regular networks and lattices where all degrees are equal, and thus the attractiveness of a node must be determined by an assigned weight, rather than the degree. We derive the complete distribution of basins of attraction resulting from randomly assigned weights in one-dimensional chains.

References in corpus (36)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Resilience of the Internet to random breakdowns
• Community detection in complex networks using Extremal Optimization
• Self-similarity of complex networks
• Breakdown of the Internet under intentional attack
• Search in Power-Law Networks
• Organization of Growing Random Networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Detecting communities in large networks
• Degree Distributions of Growing Networks
• A Local Method for Detecting Communities
• Distance, dissimilarity index, and network community structure
• Fractal and Transfractal Recursive Scale-Free Nets
• The network topology of a potential energy landscape: A static scale-free network
• Evaluating Local Community Methods in Networks
• Log-Networks
• Communication Bottlenecks in Scale-Free Networks
• Percolation in Hierarchical Scale-Free Nets
• The largest component in a subcritical random graph with a power law degree distribution
• Congestion-gradient driven transport on complex networks
• Search in Complex Networks : a New Method of Naming
• Network of inherent structures in spin glasses: scaling and scale-free distributions
• Networks with given two-point correlations: hidden correlations from degree correlations
• The Statistics of the Number of Minima in a Random Energy Landscape

Cited by in corpus (7)

• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Mean-field diffusive dynamics on weighted networks
• Covariance, correlation matrix and the multi-scale community structure of networks
• Retention capacity of random surfaces
• Retention capacity of correlated surfaces
• Communities as Well Separated Subgraphs With Cohesive Cores: Identification of Core-Periphery Structures in Link Communities
• Dynamic Space Packing