Network Landscape from a Brownian Particle's Perspective

الأصل · EN

Given a complex biological or social network, how many clusters should it be decomposed into? We define the distance dᵢ,ⱼ 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ᵢ,ⱼ≤ dᵢ,ₖ for any k of the graph; it is a local attractor of i, if j∈ Eᵢ (the set of nearest-neighbors of i) and dᵢ,ⱼ≤ dᵢ,ₗ for any l∈ Eᵢ. 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.