Extended clustering coefficients:Generalization of clustering coefficients in small-world networks

Abstract

The clustering coefficient C of a network, which is a measure of direct connectivity between neighbors of the various nodes, ranges from 0 (for no connectivity) to 1 (for full connectivity). We define extended clustering coefficients C(h) of a small-world network based on nodes that are at distance h from a source node, thus generalizing distance-1 neighborhoods employed in computing the ordinary clustering coefficient C = C(1). Based on known results about the distance distribution P _δ(h) in a network, that is, the probability that a randomly chosen pair of vertices have distance h, we derive and experimentally validate the law P _δ(h)C(h) ≤ c log N / N, where c is a small constant that seldom exceeds 1. This result is significant because it shows that the product P _δ(h)C(h) is upper-bounded by a value that is considerably smaller than the product of maximum values for P _δ(h) and C(h). Extended clustering coefficients and laws that govern them offer new insights into the structure of small-world networks and open up avenues for further exploration of their properties.

Keywords

Clustering coefficient / small-world / extended clustering coefficient / distance distribution

References

[1] Akers S.B., Krishnamurthy B.. A group theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, 38(4): 555-566.

[2] Barabási A.-L., Albert R.. Emergence of scaling in random networks. Science, 1999, 286: 509-512.

[3] Biggs, N. (1993). Algebraic Graph Theory. Cambridge Univ. Press

[4] Kim B.J., Yoon C.N., Han S.K., Jeong H.. Path finding strategies in scale-free networks. Physical Review E, 2002, 65: 027103.

[5] Milgram S.. The small world problem. Psychology Today, 1967, 1: 61-67.

[6] Montoya J.M., Sole R.V.. Small world patterns in food webs. Journal of Theoretical Biology, 2002, 214: 405-412.

[7] Myers C.R.. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs. Physical Review E, 2003, 68: 046116.

[8] Newman M.E.J.. Scientific collaboration networks. I. Network construction and fundamental results. Physical Review E, 2001, 64: 016131.

[9] Newman M.E.J.. The structure and function of complex networks. SIAM Review, 2003, 45: 167-256.

[10] Watts D.J., Strogatz S.H.. Collective dynamics of ’small-world’ networks. Nature, 1998, 393: 440-442.

[11] Xiao W.J., Parhami B.. Cayley graphs as models of deterministic small-world networks. Information Processing Letters, 2006, 97: 115-117.

[12] Xiao, W.J. & Parhami, B. (2005). On conditions for scale-freedom in complex networks. Working Paper