poster

Suggesting ghost edges for a smaller world

Authors:

Manos Papagelis,

Francesco Bonchi,

Aristides GionisAuthors Info & Claims

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

Pages 2305 - 2308

https://doi.org/10.1145/2063576.2063952

Published: 24 October 2011 Publication History

Get Access

Abstract

Small changes in the network topology can have dramatic effects on its capacity to disseminate information. In this paper, we consider the problem of adding a small number of ghost edges in the network in order to minimize the average shortest-path distance between nodes, towards a smaller-world network. We formalize the problem of suggesting ghost edges and we propose a novel method for quickly evaluating the importance of ghost edges in sparse graphs. Through experiments on real and synthetic data sets, we demonstrate that our approach performs very well, for a varying range of conditions, and it outperforms sensible baselines.

References

[1]

E. D. Demaine and M. Zadimoghaddam. Minimizing the diameter of a network using shortcut edges. In SWAT, 2010.

Digital Library

Google Scholar

[2]

K. P. Eswaran and R. E. Tarjan. Augmentation problems. SIAM J. Comput., 5(4), 1976.

Google Scholar

[3]

S. Kandula and R. Mahajan. Sampling biases in network path measurements and what to do about it. In IMC, 2009.

Digital Library

Google Scholar

[4]

J. Kleinberg. The small-world phenomenon: an algorithm perspective. In STOC, 2000.

Digital Library

Google Scholar

[5]

A. Meyerson and B. Tagiku. Minimizing average shortest path distances via shortcut edge addition. In APPROX-RANDOM, 2009.

Digital Library

Google Scholar

[6]

Y. Tian, Q. He, Q. Zhao, X. Liu, and W.-c. Lee. Boosting social network connectivity with link revival. In CIKM, 2010.

Digital Library

Google Scholar

[7]

T. Watanabe and A. Nakamura. Edge-connectivity augmentation problems. J. Comput. Syst. Sci., 35, 1987.

Digital Library

Google Scholar

Cited By

View all

Mashayekhi YKang BLijffijt JDe Bie T(2024)GREASE: Graph Imbalance Reduction by Adding Sets of EdgesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.330447836:4(1611-1623)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3304478
Liu YJian L(2024)Improving the identification effect of technical trajectory by adding ghost edges in the patent citation networkElectronic Commerce Research10.1007/s10660-024-09830-9Online publication date: 23-Mar-2024
https://doi.org/10.1007/s10660-024-09830-9
Chan HWang CAgmon NAn BRicci AYeoh W(2023)Mechanism Design for Improving Accessibility to Public FacilitiesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598885(2116-2124)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598885
Show More Cited By

Index Terms

Suggesting ghost edges for a smaller world
1. Information systems
  1. Information storage systems
    1. Storage architectures
      1. Storage network architectures

Recommendations

Refining Social Graph Connectivity via Shortcut Edge Addition

Small changes on the structure of a graph can have a dramatic effect on its connectivity. While in the traditional graph theory, the focus is on well-defined properties of graph connectivity, such as biconnectivity, in the context of a social graph, ...
Weight assignment on edges towards improved community detection
IDEAS '19: Proceedings of the 23rd International Database Applications & Engineering Symposium

During the last few decades the problem of community detection in social networks has become an important and challenging computational task. Consequently, a number of algorithms have been proposed in the relevant literature, some of which seem to solve ...
Stability of small-world networks of neural populations

At large scales the brain is a complex network of anatomical structures, or neural populations, with the small-world characteristics of dense local clustering between neighboring populations and a short path length between any two populations. There ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '11: Proceedings of the 20th ACM international conference on Information and knowledge management

October 2011

2712 pages

ISBN:9781450307178

DOI:10.1145/2063576

Editors:
Bettina Berendt,
Arjen de Vries,
Wenfei Fan,
Craig Macdonald
University of Glasgow, UK
,
Iadh Ounis
University of Glasgow, UK
,
Ian Ruthven
University of Strathclyde, UK

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

CIKM '11

Sponsor:

CIKM '11: International Conference on Information and Knowledge Management

October 24 - 28, 2011

Glasgow, Scotland, UK

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
242
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)2

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mashayekhi YKang BLijffijt JDe Bie T(2024)GREASE: Graph Imbalance Reduction by Adding Sets of EdgesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.330447836:4(1611-1623)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3304478
Liu YJian L(2024)Improving the identification effect of technical trajectory by adding ghost edges in the patent citation networkElectronic Commerce Research10.1007/s10660-024-09830-9Online publication date: 23-Mar-2024
https://doi.org/10.1007/s10660-024-09830-9
Chan HWang CAgmon NAn BRicci AYeoh W(2023)Mechanism Design for Improving Accessibility to Public FacilitiesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598885(2116-2124)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598885
Li WCai MGao MWen DQin LWang W(2023)Expanding Reverse Nearest NeighborsProceedings of the VLDB Endowment10.14778/3636218.363622017:4(630-642)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636220
Bienkowski MFuchssteiner DSchmid SMohror KArnold DBadia R(2023)Optimizing Reconfigurable Optical Datacenters: The Power of RandomizationProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607057(1-11)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607057
Hanauer KHenzinger MSchmid STrummer J(2022)Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter TopologiesIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796921(1649-1658)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796921
Haddadan SMenghini CRiondato MUpfal E(2022)Reducing polarization and increasing diverse navigability in graphs by inserting edges and swapping edge weightsData Mining and Knowledge Discovery10.1007/s10618-022-00875-836:6(2334-2378)Online publication date: 2-Oct-2022
https://doi.org/10.1007/s10618-022-00875-8
Matakos AGionis A(2022)Strengthening ties towards a highly-connected worldData Mining and Knowledge Discovery10.1007/s10618-021-00812-1Online publication date: 4-Jan-2022
https://doi.org/10.1007/s10618-021-00812-1
Du WLi GHe X(2022)Network structure optimization for social networks by minimizing the average path lengthComputing10.1007/s00607-022-01061-w104:6(1461-1480)Online publication date: 16-Feb-2022
https://doi.org/10.1007/s00607-022-01061-w
Bienkowski MFuchssteiner DMarcinkowski JSchmid S(2021)Online Dynamic B-MatchingACM SIGMETRICS Performance Evaluation Review10.1145/3453953.345397648:3(99-108)Online publication date: 5-Mar-2021
https://dl.acm.org/doi/10.1145/3453953.3453976
Show More Cited By

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Refining Social Graph Connectivity via Shortcut Edge Addition

Weight assignment on edges towards improved community detection

Stability of small-world networks of neural populations