Network Landscape from a Brownian Particle's Perspective

Abstract

Given a complex biological or social network, how many clusters should it be decomposed into? We define the distance $d_{i,j}$ from node $i$ to node $j$ as the average number of steps a Brownian particle takes to reach $j$ from $i$. Node $j$ is a global attractor of $i$ if $d_{i,j}\le d_{i,k}$ for any $k$ of the graph; it is a local attractor of $i$, if $j\in E_i$ (the set of nearest-neighbors of $i$) and $d_{i,j}\le d_{i,l}$ for any $l\in E_i$. Based on the intuition that each node should have a high probability to be in the same community as its global (local) attractor on the global (local) scale, we present a simple method to uncover a network's community structure. This method is applied to several real networks and some discussion on its possible extensions is made.

5 pages, 4 color-figures. REVTeX 4 format. To appear in PRE

References in corpus (10)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Lethality and centrality in protein networks
• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Optimal network topologies for local search with congestion
• Adaptive Random Walks on the Class of Web Graph

Cited by in corpus (27)

• Community detection in graphs
• Community detection in networks: A user guide
• Random walks and diffusion on networks
• A Method to Find Community Structures Based on Information Centrality
• Distance, dissimilarity index, and network community structure
• Social significance of community structure: Statistical view
• Characteristic times of biased random walks on complex networks
• Efficient exploration of multiplex networks
• Comparison and validation of community structures in complex networks
• A Parameterized Centrality Metric for Network Analysis
• A functional clustering algorithm for the analysis of dynamic network data
• Uncovering the community structure associated with the diffusion dynamics of networks
• Potts model based on a Markov process computation solves the community structure problem effectively
• Graph theory enables drug repurposing. How a mathematical model can drive the discovery of hidden Mechanisms of Action
• Unveiling community structures in weighted networks
• Inversion method for content-based networks
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Maximal entropy random walk in community finding
• Analysis of stability of community structure across multiple hierarchical levels
• Effect of size heterogeneity on community identification in complex networks
• An integrative dynamical perspective for graph theory and the study of complex networks
• Finding overlapping communities in networks using evolutionary method
• Inter-arrival times of message propagation on directed networks
• Detecting groups of similar components in complex networks
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Dynamics of Cluster Synchronisation in Modular Networks: Implications for Structural and Functional Networks
• Response time of lateral predictive coding and benefits of modular structures