APS Logo

Exploring Network Communities with Random Walks

ORAL

Abstract

Communities within a network are sets of nodes such that the nodes within each set are connected more densely internally than with nodes outside the set. Community structures are very common in real-world networks such as social or biological networks. Detecting community structures is equivalent to clustering which is of interest in many areas of science. We propose a computationally efficient method, based on random walks, for community detection and clustering on undirected networks with weighted or unweighted edges. The method employs first-passage properties of random walks on networks, providing key statistics of network community structure such as the number of communities and the size of each community. Our method provides a complete hierarchy of clusters which is determined by the strengths of connections between them. Surprisingly, some of the key statistics can be obtained after exploring only a small fraction of nodes which is relevant to very large real-world networks. We have used this method to cluster biological networks such as gene co-expression networks.

–

Authors

  • Aditya Ballal

    Department of Physics, Rutgers University

  • Anuradha Gupta

    New Jersey Inst of Tech, Pennsylvania State University, Bard College, University of Mississippi, Drexel Univ, Collaborator, University of Dayton, Morgan State University, Louisiana State University, University of Geneva, Instituto Superior Tecnico - Lisboa, Department of Biochemistry and Molecular Biology, Rutgers University, Institute for Quantitative Biomedicine, Rutgers University, Pennsylvania State University, and University of Illinois at Urbana-Champaign, University of Illinois at Urbana-Champaign, Department of Chemical Engineering, New Jersey Institute of Technology, Department of Physics and Astronomy, Rutgers University-New Brunswick, Department of Physics, Rutgers University, Max-Planck-Institut für Festkörperforschung, Heisenbergstrasse 1, 70569 Stuttgart, Germany, Department of Physics and Fribourg Center for Nanomaterials, University of Fribourg, Chemin du Musée 3, CH-1700 Fribourg, Switzerland, The MacDiarmid Institute for Advanced Materials and Nanotechnology, 1010 Auckland, New Zealand, Department of Physics, College of William & Mary, Williamsburg, VA 23187-8795, USA, New Jersey Institute of Technology, Newark, NJ, USA, University of California, Los Angeles, CA, USA, University of California, Berkeley, CA, USA, Space Research Institute of RAS, Moscow, Russia, Georgetown University, Institut Polytechnique de Paris, University of Delaware, Brookhaven National Laboratory, San Diego State University, University of Chicago, University of Illinois at Chicago, Argonne National Laboratory, Department of Physics and Astronomy, Rutgers University, Piscataway, NJ 08854, USA, University of Washington

  • Alexandre Morozov

    Department of Physics, Rutgers University