More Web Proxy on the site http://driver.im/

Article

Using structure indices for efficient approximation of network properties

Authors:

Matthew J. Rattigan,

David JensenAuthors Info & Claims

KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 357 - 366

https://doi.org/10.1145/1150402.1150443

Published: 20 August 2006 Publication History

Abstract

Statistics on networks have become vital to the study of relational data drawn from areas such as bibliometrics, fraud detection, bioinformatics, and the Internet. Calculating many of the most important measures - such as betweenness centrality, closeness centrality, and graph diameter-requires identifying short paths in these networks. However, finding these short paths can be intractable for even moderate-size networks. We introduce the concept of a network structure index (NSI), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. We present several varieties of NSIs, examine their time and space complexity, and analyze their performance on synthetic and real data sets. We show that creating an NSI for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.

References

[1]

L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law networks. Physical Review E, 64, 2001.

[2]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996.

Digital Library

[3]

U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25:163--177, 2001.

[4]

E. Chow. A graph search heuristic for shortest distance paths. Technical Report UCRL-JRNL-202894, Lawrence Livermore National Laboratory, 2004.

[5]

D. Coppersmith and S. Winograd. Matrix muliplication via arithmetic progressions. Journal of Symbolic Computing. 9:251--280, 1990.

Digital Library

[6]

P. Erdös and A. Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17--61. 1960.

[7]

C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004.

Digital Library

[8]

R. W. Floyd. Algorithm 97 (shortest path). Communications of the ACM, 5(6):345, 1962.

Digital Library

[9]

L. C. Freeman. Centrality in social networks: Conceptual clarification. Social Networks 1:215--239, 1979.

[10]

N. Friedman, L. Getoor, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In Proceedings of the International Joint Conference on Artificial Intelligence, 1999.

Digital Library

[11]

A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In ACM-SIAM Symposium on Discrete Algorithms, 2005.

Digital Library

[12]

J. Kleinberg. Navigation in a small world. Nature, 406:845, 2000.

[13]

J. Kleinberg. The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000.

Digital Library

[14]

J. Kleinberg, A. Slivkins, and T. Wexler. Triangulation and embedding using small sets of beacons. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004.

Digital Library

[15]

R. Krauthgamer and J. R. Lee. Navigating nets: Simple algorithms for proximity search. In ACM-SIAM Symposium on Discrete Algorithms, 2004.

Digital Library

[16]

J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2005.

Digital Library

[17]

J. Neville and D. Jensen. Dependency networks for relational data. In Proceedings of the 4th IEEE International Conference on Data Mining, 2004.

Digital Library

[18]

T. S. E. Ng and H. Zhang. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies 1:170--179, 2002.

[19]

C. R. Palmer, P. B. Gibbons, and C. Faloutsos. ANF: A fast and scalable tool for data mining in massive graphs. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002.

Digital Library

[20]

M. Pias, J. Crowcroft, S. Wilbur, T. Harris, and S. Bhatti. Lighthouses for scalable distributed location. In Proceedings of the 2nd International Workshop on Peer-To-Peer Systems, 2003.

[21]

Y. Shavitt and T. Tankel. Big-Bang simulation for embedding network distances in Euclidean space. In Proceedings of IEEE Infocom, 2003.

[22]

A. Slivkins. Distance estimation and object location via rings of neighbors. In Proceedings of the ACM Symposium on Principles of Distributed Computing, 2005.

Digital Library

[23]

Ö. Şimşek and D. Jensen. Decentralized search in networks using homophily and degree disparity. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, 2005.

Digital Library

[24]

L. Tang and M. Crovella. Virtual landmarks for the Internet. In Proceedings of the Internet Measurement Conference, 2003.

Digital Library

[25]

D. J. Watts, P. S. Dodds, and M. E. J. Newman. Identity and search in social networks. Science, 296:1302--1305, 2002.

[26]

D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.

[27]

Wikipedia contributors (2006). Six Degrees of Kevin Bacon. Wikipedia, The Free Encyclopedia. Retrieved 15:10, April 15, 2006 from http://en.wikipedia.org/w/index.php? title=Six_Degrees_of_Kevin_Bacon&oldid=48040027.

[28]

B. Wong, A. Slivkins, and E. G. Sirer. Meridian: A lightweight network location service without virtual coordinates. In Proceedings of SIGCOMM, 2005.

Digital Library

Cited By

Mondal RIgnatova EWalke DBroneske DSaake GHeyer R(2024)Clustering graph data: the roadmap to spectral techniquesDiscover Artificial Intelligence10.1007/s44163-024-00102-x4:1Online publication date: 22-Jan-2024
https://doi.org/10.1007/s44163-024-00102-x
Plana FAbeliuk APérez J(2024)Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networksComputing10.1007/s00607-024-01303-z106:8(2675-2705)Online publication date: 8-Jun-2024
https://doi.org/10.1007/s00607-024-01303-z
Nie TZhao MZhu ZZhao KWang Z(2023)Estimating feature importance in circuit network using machine learningMultimedia Tools and Applications10.1007/s11042-023-16814-8Online publication date: 15-Sep-2023
https://doi.org/10.1007/s11042-023-16814-8
Show More Cited By

Index Terms

Using structure indices for efficient approximation of network properties
1. Information systems
  1. Information retrieval
    1. Document representation
    2. Search engine architectures and scalability
      1. Search engine indexing
  2. Information systems applications
    1. Data mining

Recommendations

Indexing Network Structure with Shortest-Path Trees

The ability to discover low-cost paths in networks has practical consequences for knowledge discovery and social network analysis tasks. Many analytic techniques for networks require finding low-cost paths, but exact methods for search become ...
Emergence of global network property based on multi-agent voting model
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems

Recent studies have shown that various models can explain the emergence of complex networks, such as scale-free and small-world networks. This paper presents a different model to generate complex networks using a multi-agent approach. Each node is ...
Key Author Analysis in Research Professionals' Collaboration Network based on MST using Centrality Measures
ICTCS '16: Proceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies

The importance of an actor in the network is measured by the different type of centrality metrics of Social Network Analysis (SNA). In the research community, who are the most prominent author or key on the network is the major discussion or research ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2006

986 pages

ISBN:1595933395

DOI:10.1145/1150402

Conference Chair:
Tina Eliassi-Rad
LLNL
,
General Chair:
Lyle Ungar
University of Pennsylvania
,
Program Chairs:
Mark Craven
University of Wisconsin
,
Dimitrios Gunopulos
University of California, Riverside

Copyright © 2006 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 ACM 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: 20 August 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD06

Sponsor:

KDD06: The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 20 - 23, 2006

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
808
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mondal RIgnatova EWalke DBroneske DSaake GHeyer R(2024)Clustering graph data: the roadmap to spectral techniquesDiscover Artificial Intelligence10.1007/s44163-024-00102-x4:1Online publication date: 22-Jan-2024
https://doi.org/10.1007/s44163-024-00102-x
Plana FAbeliuk APérez J(2024)Quickcent: a fast and frugal heuristic for harmonic centrality estimation on scale-free networksComputing10.1007/s00607-024-01303-z106:8(2675-2705)Online publication date: 8-Jun-2024
https://doi.org/10.1007/s00607-024-01303-z
Nie TZhao MZhu ZZhao KWang Z(2023)Estimating feature importance in circuit network using machine learningMultimedia Tools and Applications10.1007/s11042-023-16814-8Online publication date: 15-Sep-2023
https://doi.org/10.1007/s11042-023-16814-8
冯冠(2022)The Approximate Shortest Path Algorithm for Complex Networks Based on EIN Overlay NetworkComputer Science and Application10.12677/CSA.2022.12408212:04(806-816)Online publication date: 2022
https://doi.org/10.12677/CSA.2022.124082
Potamias RNeofytou ABintsi KZafeiriou S(2022)GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)10.1109/CVPRW56347.2022.00335(2967-2976)Online publication date: Jun-2022
https://doi.org/10.1109/CVPRW56347.2022.00335
Singh R(2021)Centrality Measures: A Tool to Identify Key Actors in Social NetworksPrinciples of Social Networking10.1007/978-981-16-3398-0_1(1-27)Online publication date: 19-Aug-2021
https://doi.org/10.1007/978-981-16-3398-0_1
Jiang LLai YChen QZeng WYang FYi F(2021)Shortest Path Distance Prediction Based on CatBoostWeb Information Systems and Applications10.1007/978-3-030-87571-8_12(133-143)Online publication date: 17-Sep-2021
https://doi.org/10.1007/978-3-030-87571-8_12
Mensah DGao HYang L(2020)Approximation Algorithm for Shortest Path in Large Social NetworksAlgorithms10.3390/a1302003613:2(36)Online publication date: 6-Feb-2020
https://doi.org/10.3390/a13020036
van der Grinten AAngriman EMeyerhenke H(2020)Scaling up network centrality computations – A brief overviewit - Information Technology10.1515/itit-2019-003262:3-4(189-204)Online publication date: 11-Mar-2020
https://doi.org/10.1515/itit-2019-0032
Gu KLiu DWang K(2019)Social Community Detection Scheme Based on Social-Aware in Mobile Social NetworksIEEE Access10.1109/ACCESS.2019.29561497(173407-173418)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2956149
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents