research-article

Public Access

The Local Closure Coefficient: A New Perspective On Network Clustering

Authors:

Austin R. Benson,

Jure LeskovecAuthors Info & Claims

WSDM '19: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining

Pages 303 - 311

https://doi.org/10.1145/3289600.3290991

Published: 30 January 2019 Publication History

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.

References

[1]

Dblp network dataset -- KONECT, Apr. 2017.

[2]

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.

[3]

L. Akoglu, M. McGlohon, and C. Faloutsos. Oddball: Spotting anomalies in weighted graphs. In PAKDD, 2010.

Digital Library

[4]

L. Akoglu, H. Tong, and D. Koutra. Graph based anomaly detection and description: a survey. Data Mining and Knowledge Discovery, 2015.

Digital Library

[5]

P. S. Bearman and J. Moody. Suicide and friendships among american adolescents. Am. J. Public Health, 2004.

[6]

A. R. Benson, D. F. Gleich, and J. Leskovec. Higher-order organization of complex networks. Science, 2016.

[7]

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.

[8]

D. Easley and J. Kleinberg. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.

[9]

G. Fagiolo. Clustering in complex directed networks. Physical Review E, 76(2):026107, 2007.

[10]

S. Fortunato. Community detection in graphs. Phys. Rep, 2010.

[11]

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.

[12]

M. Girvan and M. E. Newman. Community structure in social and biological networks. PNAS, 2002.

[13]

D. F. Gleich and C. Seshadhri. Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. In KDD, 2012.

Digital Library

[14]

R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In WWW, 2004.

Digital Library

[15]

F. Harary et al. On the notion of balance of a signed graph. The Michigan Mathematical Journal, 1953.

[16]

F. Heider. Attitudes and cognitive organization. The J. of Psychology, 1946.

[17]

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.

Digital Library

[18]

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.

[19]

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.

[20]

E. M. Jin, M. Girvan, and M. E. J. Newman. Structure of growing social networks. PRE, 2001.

[21]

M. Kaiser. Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks. New J. Phys., 2008.

[22]

B. Klimt and Y. Yang. Introducing the enron corpus. In CEAS, 2004.

[23]

T. LaFond, J. Neville, and B. Gallagher. Anomaly detection in networks with changing trends. In ODD$^2$ Workshop, 2014.

[24]

J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In KDD, 2008.

Digital Library

[25]

J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In CHI, 2010.

Digital Library

[26]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, 2005.

Digital Library

[27]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. TKDD, 2007.

Digital Library

[28]

D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 2007.

Digital Library

[29]

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.

[30]

A. Mislove, H. S. Koppula, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Growth of the flickr social network. In WOSN, 2008.

Digital Library

[31]

M. E. Newman. Assortative mixing in networks. PRL, 2002.

[32]

M. E. Newman, S. H. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. PRE, 2001.

[33]

M. E. J. Newman. The structure and function of complex networks. SIAM Rev., 2003.

Digital Library

[34]

T. Opsahl and P. Panzarasa. Clustering in weighted networks. Social networks, 31(2):155--163, 2009.

[35]

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.

Digital Library

[36]

A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In WSDM, 2017.

Digital Library

[37]

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.

[38]

A. Rapoport. Spread of information through a population with socio-structural bias: I. assumption of transitivity. The Bull. of Math. Biophysics, 1953.

[39]

E. Ravasz and A.-L. Barabási. Hierarchical organization in complex networks. PRE, 2003.

[40]

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.

[41]

P. Robles, S. Moreno, and J. Neville. Sampling of attributed networks from hierarchical generative models. In KDD, 2016.

Digital Library

[42]

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.

[43]

S. E. Schaeffer. Graph clustering. Computer Science Review, 2007.

Digital Library

[44]

C. Seshadhri, T. G. Kolda, and A. Pinar. Community structure and scale-free collections of erdHo s-rényi graphs. PRE, 2012.

[45]

S. N. Soffer and A. Vázquez. Network clustering coefficient without degree-correlation biases. PRE, 2005.

[46]

A. L. Traud, P. J. Mucha, and M. A. Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 2012.

[47]

A. Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. PRE, 2003.

[48]

A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the internet. PRE, 2002.

[49]

S. Wasserman and K. Faust. Social network analysis: Methods and applications, volume 8. Cambridge university press, 1994.

[50]

D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 1998.

[51]

Z.-X. Wu and P. Holme. Modeling scientific-citation patterns and other triangle-rich acyclic networks. PRE, 2009.

[52]

J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 2015.

Digital Library

[53]

H. Yin, A. R. Benson, and J. Leskovec. Higher-order clustering in networks. Physical Review E, 97(5):052306, 2018.

[54]

H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich. Local higher-order graph clustering. In KDD, 2017.

Digital Library

Cited By

Sidorov SEmelianov TMironov SSidorova EKostyukhin YVolkov AOstrovskaya APolezharova L(2024)Network Evolution Model with Preferential Attachment at Triadic Formation StepMathematics10.3390/math1205064312:5(643)Online publication date: 22-Feb-2024
https://doi.org/10.3390/math12050643
Fu TWei CWang YYing RAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)DeSCo: Towards Generalizable and Scalable Deep Subgraph CountingProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635788(218-227)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635788
Backhausz ÁBognár ECsiszár VTárkányi DZempléni A(2024)Estimating the parameters of epidemic spread on two-layer random graphs: a classical and a neural network approachJournal of Statistical Theory and Practice10.1007/s42519-024-00405-318:4Online publication date: 19-Sep-2024
https://doi.org/10.1007/s42519-024-00405-3
Show More Cited By

Index Terms

The Local Closure Coefficient: A New Perspective On Network Clustering
1. Information systems
  1. Information systems applications
    1. Data mining
  2. World Wide Web
    1. Web applications
      1. Social networks

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 9479

In 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 informatics

Nodes 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 Research

The 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSDM '19: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining

January 2019

874 pages

ISBN:9781450359405

DOI:10.1145/3289600

General Chairs:
J. Shane Culpepper
RMIT University
,
Alistair Moffat
The University of Melbourne
,
Program Chairs:
Paul N. Bennett
Microsoft
,
Kristina Lerman
University of Southern California

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 January 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
Chan Zuckerberg Biohub
Stanford Data Science Initiative
JD
Army Research Office

Conference

WSDM '19

Sponsor:

WSDM '19: The Twelfth ACM International Conference on Web Search and Data Mining

February 11 - 15, 2019

Melbourne VIC, Australia

Acceptance Rates

WSDM '19 Paper Acceptance Rate 84 of 511 submissions, 16%;

Overall Acceptance Rate 498 of 2,863 submissions, 17%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
1,051
Total Downloads

Downloads (Last 12 months)201
Downloads (Last 6 weeks)37

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sidorov SEmelianov TMironov SSidorova EKostyukhin YVolkov AOstrovskaya APolezharova L(2024)Network Evolution Model with Preferential Attachment at Triadic Formation StepMathematics10.3390/math1205064312:5(643)Online publication date: 22-Feb-2024
https://doi.org/10.3390/math12050643
Fu TWei CWang YYing RAngélica LLattanzi SMuñoz Medina AAkoglu LGionis AVassilvitskii S(2024)DeSCo: Towards Generalizable and Scalable Deep Subgraph CountingProceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3635788(218-227)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1145/3616855.3635788
Backhausz ÁBognár ECsiszár VTárkányi DZempléni A(2024)Estimating the parameters of epidemic spread on two-layer random graphs: a classical and a neural network approachJournal of Statistical Theory and Practice10.1007/s42519-024-00405-318:4Online publication date: 19-Sep-2024
https://doi.org/10.1007/s42519-024-00405-3
Yuan M(2024)Central limit theorem for the average closure coefficientActa Mathematica Hungarica10.1007/s10474-024-01416-z172:2(543-569)Online publication date: 13-Mar-2024
https://doi.org/10.1007/s10474-024-01416-z
Su H(2024)Exploring the Threshold Effects in User-User Networks: Insights from MovieLens DataAdvanced Intelligent Technologies and Sustainable Society10.1007/978-981-97-3210-4_31(385-394)Online publication date: 11-Aug-2024
https://doi.org/10.1007/978-981-97-3210-4_31
Ugander JYin H(2023)Randomized graph cluster randomizationJournal of Causal Inference10.1515/jci-2022-001411:1Online publication date: 25-May-2023
https://doi.org/10.1515/jci-2022-0014
Tahmooresnejad LTurkina E(2023)Economic geography of innovation: The effect of gender-related aspects of co-inventor networks on country and regional innovationPLOS ONE10.1371/journal.pone.028884318:7(e0288843)Online publication date: 27-Jul-2023
https://doi.org/10.1371/journal.pone.0288843
Zhang CXiang WGuo XZhou BYang D(2023)SubAnom: Efficient Subgraph Anomaly Detection Framework over Dynamic Graphs2023 IEEE International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW60847.2023.00154(1178-1185)Online publication date: 4-Dec-2023
https://doi.org/10.1109/ICDMW60847.2023.00154
Jia MGabrys BMusial K(2023)A Network Science Perspective of Graph Convolutional Networks: A SurveyIEEE Access10.1109/ACCESS.2023.326879711(39083-39122)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3268797
Huang YLiu QLiu JHu Y(2023)Topic Discovery in Scientific LiteratureComputer Supported Cooperative Work and Social Computing10.1007/978-981-99-2356-4_38(481-491)Online publication date: 13-May-2023
https://doi.org/10.1007/978-981-99-2356-4_38
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents