EUVIMEDEUVIMED entdecken
Crossref

Local rewiring algorithms to increase clustering and grow a small world

Jeff Alstott, Christine Klymko, Pamela B Pyzza, Mary Radcliffe

Journal of Complex Networks · 01.08.2019 · 7 (4) · 564-584

DOI: 10.1093/comnet/cny032 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Complex Networks, online erschienen am 17.12.2018. Verfasst von Jeff Alstott und 3 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 39 Literaturangaben. Gefördert von: SUTD-MIT Postdoctoral Programme, U.S. Department of Energy, Lawrence Livermore National Laboratory.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Many real-world networks have high clustering among vertices: vertices that share neighbours are often also directly connected to each other. A network’s clustering can be a useful indicator of its connectedness and community structure. Algorithms for generating networks with high clustering have been developed, but typically rely on adding or removing edges and nodes, sometimes from a completely empty network. Here, we introduce algorithms that create a highly clustered network by starting with an existing network and rearranging edges, without adding or removing them; these algorithms can preserve other network properties even as the clustering increases. They rely on local rewiring rules, in which a single edge changes one of its vertices in a way that is guaranteed to increase clustering. This greedy step can be applied iteratively to transform a random network into a form with much higher clustering. Additionally, the algorithms presented grow a network’s clustering faster than they increase its path length, meaning that network enters a regime of comparatively high clustering and low path length: a small world. These algorithms may be a basis for how real-world networks rearrange themselves organically to achieve or maintain high clustering and small-world structure.

Förderung

  • SUTD-MIT Postdoctoral Programme
  • U.S. Department of Energy
  • Lawrence Livermore National Laboratory

Zitieren

APA

Alstott, J., Klymko, C., Pyzza, P. B., & Radcliffe, M. (2019). Local rewiring algorithms to increase clustering and grow a small world. Journal of Complex Networks, 7(4), 564-584. https://doi.org/10.1093/comnet/cny032

Vancouver

Alstott J, Klymko C, Pyzza PB, Radcliffe M. Local rewiring algorithms to increase clustering and grow a small world. Journal of Complex Networks. 2019;7(4):564-584. doi:10.1093/comnet/cny032

BibTeX
@article{Alstott2019,
  author = {Alstott, Jeff and Klymko, Christine and Pyzza, Pamela B and Radcliffe, Mary},
  title = {Local rewiring algorithms to increase clustering and grow a small world},
  journal = {Journal of Complex Networks},
  year = {2019},
  volume = {7},
  number = {4},
  pages = {564--584},
  doi = {10.1093/comnet/cny032}
}
Kostenlos starten →