skip to main content
10.1145/3038912.3052635acmotherconferencesArticle/Chapter ViewAbstractPublication PageswwwConference Proceedingsconference-collections
research-article
Public Access

The k-peak Decomposition: Mapping the Global Structure of Graphs

Published:03 April 2017Publication History

ABSTRACT

The structure of real-world complex networks has long been an area of interest, and one common way to describe the structure of a network has been with the k-core decomposition. The core number of a node can be thought of as a measure of its centrality and importance, and is used by applications such as community detection, understanding viral spreads, and detecting fraudsters. However, we observe that the k-core decomposition suffers from an important flaw: namely, it is calculated globally, and so if the network contains distinct regions of different densities, the sparser among these regions may be neglected.

To resolve this issue, we propose the k-peak graph decomposition method, based on the k-core algorithm, which finds the centers of distinct regions in the graph. Our contributions are as follows: (1) We present a novel graph decomposition- the k-peak decomposition- and corresponding algorithm, and perform a theoretical analysis of its properties. (2) We describe a new visualization method, the "Mountain Plot", which can be used to better understand the global structure of a graph. (3) We perform an extensive empirical analysis of real-world graphs, including technological, social, biological, and collaboration graphs, and show how the k-peak decomposition gives insight into the structures of these graphs. (4) We demonstrate the advantage of using the k-peak decomposition in various applications, including community detection, contagion and identifying essential proteins.

References

  1. KONECT: The koblenz network collection. http://konect.uni-koblenz.de/networks, May 2015.Google ScholarGoogle Scholar
  2. J. Abello and F. Queyroi. Fixed points of graph peeling. In Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on, pages 256--263. IEEE, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. V. Batagelj and M. Zaversnik. An O(m) algorithm for cores decomposition of networks. Advances in Data Analysis and Classification, 5(2):129--145, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. S. P. Borgatti and M. G. Everett. Social Networks, pages 375--395, 2000.Google ScholarGoogle Scholar
  5. J. Cohen. Trusses: Cohesive subgraphs for social network analysis. 2008.Google ScholarGoogle Scholar
  6. S. A. Erdem, C. Seshadhri, A. Pinar, and U. V. Catalyurek. Finding the hierarchy of dense subgraphs using nucleus decompositions. In WWW, 2015. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. P. Govindan, S. Soundarajan, T. Eliassi-Rad, and C. Faloutsos. Nimblecore: A space-efficient external memory algorithm for estimating core numbers. In ASONAM, 2016.Google ScholarGoogle ScholarCross RefCross Ref
  8. P. Holme. Core-periphery organization of complex networks. Physical Review E, 72(4):046111, 2005.Google ScholarGoogle ScholarCross RefCross Ref
  9. J. Jiang, M. Mitzenmacher, and J. Thaler. Parallel peeling algorithms. ACM Trans. Parallel Comput., 3(1):7:1--7:27, Aug. 2016. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. H. Kim, J. Shin, E. Kim, H. Kim, S. Hwang, J. E. Shim, and I. Lee. Yeastnet v3: a public database of data-specific and integrated functional gene networks for saccharomyces cerevisiae. Nucleic Acids Research, 42:731--736, 2014.Google ScholarGoogle ScholarCross RefCross Ref
  11. M. Kitsak, L. Gallos, S. Havlin, F. Liljeros, L. Muchnik, E. Stanley, and H. Makse. Identification of influential spreaders in complex networks. Nature Physics, 6(11):888--893, 2010.Google ScholarGoogle ScholarCross RefCross Ref
  12. J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google ScholarGoogle Scholar
  13. Y. Liu, N. Shah, and D. Koutra. An empirical comparison of the summarization power of graph clustering methods. CoRR, 2015.Google ScholarGoogle Scholar
  14. A. Mislove, B. Viswanath, K. P. Gummadi, and P. Druschel. You are who you know: Inferring user profiles in online social networks. In WSDM, pages 251--260, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. A. Montresor, F. D. Pellegrini, and D. Miorandi. Distributed k-core decomposition. IEEE TPDS, 24(2):288--300, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. M. P. O'Brien and B. D. Sullivan. Locally estimating core numbers. In ICDM, pages 460--469, 2014. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. C. Peng, T. G. Kolda, and A. Pinar. Accelerating community detection by using k-core subgraphs. CoRR, abs/1403.2226, 2014.Google ScholarGoogle Scholar
  18. M. P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha. Core-periphery structure in networks. SIAM Journal on Applied Mathematics, pages 167--190, 2014.Google ScholarGoogle Scholar
  19. A. E. Saríıyüce, B. Gedik, G. Jacques-Silva, K.-L. Wu, and U. V. Çatalyürek. Streaming algorithms for k-core decomposition. PVLDB, 6(6):433--444, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269--287, 1983.Google ScholarGoogle ScholarCross RefCross Ref
  21. J. Ugander, B. Karrer, L. Backstrom, and J. M. Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In KDD, pages 329--337, 2013. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. N. Wang, S. Parthasarathy, K. Tan, and A. K. H. Tung. CSV: visualizing and mining cohesive subgraphs. In SIGMOD, pages 445--458, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. S. Wuchty and E. Almaas. Peeling the yeast protein network. Proteomics, 5(2):444--449, 2005.Google ScholarGoogle ScholarCross RefCross Ref
  24. X. Zhang, T. Martin, and M. E. Newman. Identification of core-periphery structure in networks. Physical Review E, 91(3):032803, 2015.Google ScholarGoogle ScholarCross RefCross Ref
  25. X. Zhang, J. Xu, and W. xin Xiao. A new method for the discovery of essential proteins. PLoS One, 8(3), 2013.Google ScholarGoogle Scholar

Index Terms

  1. The k-peak Decomposition: Mapping the Global Structure of Graphs

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Other conferences
        WWW '17: Proceedings of the 26th International Conference on World Wide Web
        April 2017
        1678 pages
        ISBN:9781450349130

        Copyright © 2017 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

        Publisher

        International World Wide Web Conferences Steering Committee

        Republic and Canton of Geneva, Switzerland

        Publication History

        • Published: 3 April 2017

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        WWW '17 Paper Acceptance Rate164of966submissions,17%Overall Acceptance Rate1,899of8,196submissions,23%

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader