Local rewiring algorithms to increase clustering and grow a small world
From MaRDI portal
(Redirected from Local rewiring algorithms to increase clustering and grow a small world)
Abstract: Many real-world networks have high clustering among vertices: vertices that share neighbors 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.
Recommendations
Cited in
(2)
This page was built for publication: Local rewiring algorithms to increase clustering and grow a small world
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958773)
