Hao Yin
Jure Leskovec
ABSTRACT
The phenomenon of edge clustering in real-world networks is a fundamental property underlying many ideas and techniques in network science. Clustering is typically quantified by the clustering coefficient, which measures the fraction of pairs of neighbors of a given center node that are connected. However, many common explanations of edge clustering attribute the triadic closure to a head node instead of the center node of a length-2 path; for example, a friend of my friend is also my friend. While such explanations are common in network analysis, there is no measurement for edge clustering that can be attributed to the head node. Here we develop local closure coefficients as a metric quantifying head-node-based edge clustering. We define the local closure coefficient as the fraction of length-2 paths emanating from the head node that induce a triangle. This subtle difference in definition leads to remarkably different properties from traditional clustering coefficients. We analyze correlations with node degree, connect the closure coefficient to community detection, and show that closure coefficients as a feature can improve link prediction.
- Dblp network dataset -- KONECT, Apr. 2017.Google Scholar
- N. K. Ahmed, R. A. Rossi, J. B. Lee, X. Kong, T. L. Willke, R. Zhou, and H. Eldardiry. Learning role-based graph embeddings. arXiv, 2018.Google Scholar
- L. Akoglu, M. McGlohon, and C. Faloutsos. Oddball: Spotting anomalies in weighted graphs. In PAKDD, 2010. Google ScholarDigital Library
- L. Akoglu, H. Tong, and D. Koutra. Graph based anomaly detection and description: a survey. Data Mining and Knowledge Discovery, 2015. Google ScholarDigital Library
- P. S. Bearman and J. Moody. Suicide and friendships among american adolescents. Am. J. Public Health, 2004.Google ScholarCross Ref
- A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 2016.Google Scholar
- E. Cozzo, M. Kivel"a, M. De Domenico, A. Solé-Ribalta, A. Arenas, S. Gómez, M. A. Porter, and Y. Moreno. Structure of triadic relations in multiplex networks. New Journal of Physics, 17(7):073029, 2015.Google ScholarCross Ref
- D. Easley and J. Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010. Google ScholarCross Ref
- G. Fagiolo. Clustering in complex directed networks. Physical Review E, 76(2):026107, 2007.Google ScholarCross Ref
- S. Fortunato. Community detection in graphs. Phys. Rep, 2010.Google ScholarCross Ref
- B. K. Fosdick, D. B. Larremore, J. Nishimura, and J. Ugander. Configuring random graph models with fixed degree sequences. SIAM Review, 60(2):315--355, 2018.Google ScholarCross Ref
- M. Girvan and M. E. Newman. Community structure in social and biological networks. PNAS, 2002.Google ScholarCross Ref
- D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In KDD, 2012. Google ScholarDigital Library
- R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In WWW, 2004. Google ScholarDigital Library
- F. Harary et al. On the notion of balance of a signed graph. The Michigan Mathematical Journal, 1953.Google ScholarCross Ref
- F. Heider. Attitudes and cognitive organization. The J. of Psychology, 1946.Google ScholarCross Ref
- K. Henderson, B. Gallagher, T. Eliassi-Rad, H. Tong, S. Basu, L. Akoglu, D. Koutra, C. Faloutsos, and L. Li. Rolx: structural role extraction & mining in large graphs. In KDD, 2012. Google ScholarDigital Library
- M. O. Jackson and B. W. Rogers. Meeting strangers and friends of friends: How random are social networks? American Economic Review, 97(3):890--915, 2007.Google ScholarCross Ref
- L. G. Jeub, P. Balachandran, M. A. Porter, P. J. Mucha, and M. W. Mahoney. Think locally, act locally: Detection of small, medium-sized, and large communities in large networks. Physical Review E, 91(1):012821, 2015.Google ScholarCross Ref
- E. M. Jin, M. Girvan, and M. E. J. Newman. Structure of growing social networks. PRE, 2001.Google ScholarCross Ref
- M. Kaiser. Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks. New J. Phys., 2008.Google ScholarCross Ref
- B. Klimt and Y. Yang. Introducing the enron corpus. In CEAS, 2004.Google Scholar
- T. LaFond, J. Neville, and B. Gallagher. Anomaly detection in networks with changing trends. In ODD$^2$ Workshop, 2014.Google Scholar
- J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In KDD, 2008. Google ScholarDigital Library
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In CHI, 2010. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, 2005. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. TKDD, 2007. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 2007. Google ScholarDigital Library
- R. Milo, N. Kashtan, S. Itzkovitz, M. E. J. Newman, and U. Alon. On the uniform generation of random graphs with prescribed degree sequences. arXiv, 2003.Google Scholar
- A. Mislove, H. S. Koppula, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Growth of the flickr social network. In WOSN, 2008. Google ScholarDigital Library
- M. E. Newman. Assortative mixing in networks. PRL, 2002.Google ScholarCross Ref
- M. E. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. PRE, 2001.Google ScholarCross Ref
- M. E. J. Newman. The structure and function of complex networks. SIAM Rev., 2003.Google ScholarDigital Library
- T. Opsahl and P. Panzarasa. Clustering in weighted networks. Social networks, 31(2):155--163, 2009.Google ScholarCross Ref
- P. Panzarasa, T. Opsahl, and K. M. Carley. Patterns and dynamics of users' behavior and interaction: Network analysis of an online community. J. Assoc. Inf. Sci. Technol., 2009. Google ScholarDigital Library
- A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In WSDM, 2017. Google ScholarDigital Library
- M. A. Porter, P. J. Mucha, M. E. J. Newman, and C. M. Warmbrand. A network analysis of committees in the U.S. House of Representatives. PNAS, 2005.Google Scholar
- A. Rapoport. Spread of information through a population with socio-structural bias: I. assumption of transitivity. The Bull. of Math. Biophysics, 1953.Google ScholarCross Ref
- E. Ravasz and A.-L. Barabási. Hierarchical organization in complex networks. PRE, 2003.Google ScholarCross Ref
- E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabási. Hierarchical organization of modularity in metabolic networks. Science, 2002.Google Scholar
- P. Robles, S. Moreno, and J. Neville. Sampling of attributed networks from hierarchical generative models. In KDD, 2016. Google ScholarDigital Library
- D. M. Romero and J. M. Kleinberg. The directed closure process in hybrid social-information networks, with an analysis of link formation on twitter. In ICWSM, 2010.Google Scholar
- S. E. Schaeffer. Graph clustering. Computer Science Review, 2007.Google ScholarDigital Library
- C. Seshadhri, T. G. Kolda, and A. Pinar. Community structure and scale-free collections of erdHo s-rényi graphs. PRE, 2012.Google Scholar
- S. N. Soffer and A. Vázquez. Network clustering coefficient without degree-correlation biases. PRE, 2005.Google ScholarCross Ref
- A. L. Traud, P. J. Mucha, and M. A. Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 2012.Google Scholar
- A. Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. PRE, 2003.Google ScholarCross Ref
- A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the internet. PRE, 2002.Google ScholarCross Ref
- S. Wasserman and K. Faust. Social network analysis: Methods and applications, volume 8. Cambridge university press, 1994.Google ScholarCross Ref
- D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 1998.Google Scholar
- Z.-X. Wu and P. Holme. Modeling scientific-citation patterns and other triangle-rich acyclic networks. PRE, 2009.Google ScholarCross Ref
- J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 2015. Google ScholarDigital Library
- H. Yin, A. R. Benson, and J. Leskovec. Higher-order clustering in networks. Physical Review E, 97(5):052306, 2018.Google ScholarCross Ref
- H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich. Local higher-order graph clustering. In KDD, 2017. Google ScholarDigital Library
Index Terms
- The Local Closure Coefficient: A New Perspective On Network Clustering
Recommendations
Local Clustering Coefficient in Generalized Preferential Attachment Models
WAW 2015: Proceedings of the 12th International Workshop on Algorithms and Models for the Web Graph - Volume 9479In this paper, we analyze the local clustering coefficient of preferential attachment models. A general approach to preferential attachment was introduced in [19], where a wide class of models PA-class was defined in terms of constraints that are ...
A local recovery routing protocol with clustering coefficient
AIC'10/BEBI'10: Proceedings of the 10th WSEAS international conference on applied informatics and communications, and 3rd WSEAS international conference on Biomedical electronics and biomedical informaticsNodes in ad hoc networks communicate with other nodes via wireless multi-hop links. In on-demand routing protocol, nodes want to send data will provide route discovery to find routes. Route discovery is typically performed via flooding, which consumes a ...
A Clustering Algorithm for Automatically Determining the Number of Clusters Based on Coefficient of Variation
ICBDR '18: Proceedings of the 2nd International Conference on Big Data ResearchThe k-means algorithm is a typical clustering algorithm based on partition. The k-means++ algorithm is a high-quality clustering algorithm, and it is used to solve the problem that the traditional k-means algorithm is sensitive to initial centers. ...
Comments