Small world networks and clustered small world net

Authors: Faraz Zaidi

Publish Date: 2012/02/21

Volume: 3, Issue: 1, Pages: 51-63

PDF Link

Abstract

The discovery of small world properties in realworld networks has revolutionized the way we analyze and study realworld systems Mathematicians and physicists in particular have closely studied and developed several models to artificially generate networks with small world properties The classical algorithms to produce these graphs artificially make use of the fact that with the introduction of some randomness in ordered graphs small world graphs can be produced In this paper we present a novel algorithm to generate graphs with small world properties based on the idea that with the introduction of some order in a random graph small world graphs can be generated Our model starts with a randomly generated graph We then replace each node of the random graph with cliques of different sizes This ensures that the connectivity between the cliques is random but the clustering coefficient increases to a desired level We further extend this model to incorporate the property of community structures clusters found readily in realworld networks such as social biological and technological networks These community structures are densely connected regions of nodes in a network that are loosely connected to each other The model generates these clustered small world graphs by replacing nodes in the random graph with densely connected set of nodes Experimentation shows that these two models generate small world and clustered small world graphs respectively as we were able to produce the desired properties of a small world network with high clustering coefficient and low average path lengths in both cases Furthermore we also calculated relative density and modularity to show that the clustered networks indeed had community structures

Keywords: