Local rewiring algorithms to increase clustering and grow a small world. (17th December 2018)

• Record Type: Journal Article
• Authors: Alstott, Jeff; Klymko, Christine; Pyzza, Pamela B; Radcliffe, Mary
• Editors: Moore, Cristopher
• Is Part Of: Journal of complex networks. Volume 7:Number 4(2019)
• Page Start: 564
• Page End: 584
• Publication Date: 2018-12-17
• Subjects: clustering coefficient -- small world -- clustering -- triangles; 34K30 -- 35K57 -- 35Q80 -- 92D25; Numerical analysis -- Periodicals; Computer networks -- Periodicals; Social networks -- Periodicals; 518.05
• DOI: 10.1093/comnet/cny032
• Languages: English
• ISSNs: 2051-1310

Abstract

Abstract: 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.