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.
- KONECT: The koblenz network collection. http://konect.uni-koblenz.de/networks, May 2015.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- S. P. Borgatti and M. G. Everett. Social Networks, pages 375--395, 2000.Google Scholar
- J. Cohen. Trusses: Cohesive subgraphs for social network analysis. 2008.Google Scholar
- S. A. Erdem, C. Seshadhri, A. Pinar, and U. V. Catalyurek. Finding the hierarchy of dense subgraphs using nucleus decompositions. In WWW, 2015. Google ScholarDigital Library
- 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 ScholarCross Ref
- P. Holme. Core-periphery organization of complex networks. Physical Review E, 72(4):046111, 2005.Google ScholarCross Ref
- J. Jiang, M. Mitzenmacher, and J. Thaler. Parallel peeling algorithms. ACM Trans. Parallel Comput., 3(1):7:1--7:27, Aug. 2016. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google Scholar
- Y. Liu, N. Shah, and D. Koutra. An empirical comparison of the summarization power of graph clustering methods. CoRR, 2015.Google Scholar
- 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 ScholarDigital Library
- A. Montresor, F. D. Pellegrini, and D. Miorandi. Distributed k-core decomposition. IEEE TPDS, 24(2):288--300, 2013. Google ScholarDigital Library
- M. P. O'Brien and B. D. Sullivan. Locally estimating core numbers. In ICDM, pages 460--469, 2014. Google ScholarDigital Library
- C. Peng, T. G. Kolda, and A. Pinar. Accelerating community detection by using k-core subgraphs. CoRR, abs/1403.2226, 2014.Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- S. B. Seidman. Network structure and minimum degree. Social Networks, 5(3):269--287, 1983.Google ScholarCross Ref
- 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 ScholarDigital Library
- N. Wang, S. Parthasarathy, K. Tan, and A. K. H. Tung. CSV: visualizing and mining cohesive subgraphs. In SIGMOD, pages 445--458, 2008. Google ScholarDigital Library
- S. Wuchty and E. Almaas. Peeling the yeast protein network. Proteomics, 5(2):444--449, 2005.Google ScholarCross Ref
- X. Zhang, T. Martin, and M. E. Newman. Identification of core-periphery structure in networks. Physical Review E, 91(3):032803, 2015.Google ScholarCross Ref
- X. Zhang, J. Xu, and W. xin Xiao. A new method for the discovery of essential proteins. PLoS One, 8(3), 2013.Google Scholar
Index Terms
The k-peak Decomposition: Mapping the Global Structure of Graphs
Recommendations
Incremental k-core decomposition: algorithms and evaluation
A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, ...
Sandwiching a densest subgraph by consecutive cores
In this paper, we show that in the random graph Gn,c/n, with high probability, there exists an integer kï such that a subgraph of Gn,c/n, whose vertex set differs from a densest subgraph of Gn,c/n by Olog2n vertices, is sandwiched by the kï and the kï +...
Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex v r-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the ...
Comments