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 (13)

• Uncovering the overlapping community structure of complex networks in nature and society
• 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
• New Model of Internet Topology Using k-shell Decomposition
• Fractal and Transfractal Recursive Scale-Free Nets
• Evaluating Local Community Methods in 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
• The Statistics of the Number of Minima in a Random Energy Landscape

Cited by in corpus (2)

• Covariance, correlation matrix and the multi-scale community structure of networks
• Dynamic Space Packing