We extend the standard scale-free network model to include a ''triad formation step.'' We analyze the geometric properties of networks generated by this algorithm both analytically and by numerical calculations, and find that our model possesses the same characteristics as the standard scale-free networks such as the power-law degree distribution and the small average geodesic length, but with the high clustering at the same time. In our model, the clustering coefficient is also shown to be tunable simply by changing a control parameter-the average number of triad formation trials per time step. DOI: 10.1103/PhysRevE.65.026107 PACS number͑s͒: 89.75.Fb, 89.75.Hc, 89.65.Ϫs A great number of systems in many branches of science can be modeled as large sparse graphs, sharing many geometrical properties ͓1͔. For example: social networks, computer networks, and metabolic networks of certain organisms all have a logarithmically growing average geodesic ͑shortest path͒ length l and an approximately algebraically decaying distribution of vertex degree. In addition to this, social networks typically show a high clustering, or local transitivity: If person A knows B and C, then B and C are likely to know each other. Works on the geometry of social networks, which is the main focus of the present paper, have originated from Rapoport's studies of disease spreading ͓2͔, and have been further developed in Refs. ͓3,4͔. General mathematical models for random graphs with a structural bias are called the Markov graphs and were studied in Ref. ͓5͔. In the physics literature, networks with high clustering are commonly modeled by the small-world network model of Watts and Strogatz ͑WS͒ ͓6͔, while networks with the power-law degree distribution by the scale-free network model of Barabási and Albert ͑BA͒ ͓7͔. Although both models have a logarithmically increasing l with the network size, each model lacks the property of the other model: the WS model shows a high clustering but without the power-law degree distribution, while the BA model with the scale-free nature does not possess the high clustering. In this work, we propose a network model that has both the perfect power-law degree distribution and the high clustering. Furthermore, in our model, the degree of the clustering, measured by the clustering coefficient ͑see below͒, is shown to be tunable and thus controllable by adjusting a parameter of the model. We start from the definition of a network as a graph G ϭ(V,E ), where V is the set of vertices and E is the set of edges ͓8͔. An edge connects pairs of vertices in V and not more than one edge may connect a specific pair of vertices. To quantify the clustering, Watts and Strogatz introduced the clustering coefficient ␥ϵ͗␥ v ͘ with the average ͗¯͘ for all vertices in V. The local clustering coefficient
In 2002, Holme and Kim REF extended the Barabási and Albert model to include a "triad formation step." The Holme and Kim model creates networks with both the perfect power-law degree distribution and high clustering.
Growing scale-free networks with tunable clustering
Phys. Rev. E 65, 026107 (2002).
Medicine Physics Mathematics