Detecting Global Efficiency in Complex Networks Using Local Measurements and Neighborhood Information

• Cinara Guellner Ghedini ITA
• Carlos H. C. Ribeiro ITA

Abstract

Complex networks model real networks found in a wide range of domains from biological and social to technological environments. Their nature inherently dynamical emerges from ubiquitous and autonomic characteristics. Thus, assessing their behavior when dealing with failure and attacks is relevant to define mechanisms of control and recovery. However, practical aspects makes global metrics not measurable. Moreover, standard local metrics are not suitable to deal with global properties. In this paper, we present a new local metric to detect global changes in complex networks using local neighborhood information. The results show that the proposed metric accomplished satisfactory results for scale-free, small-world and random networks.

References

Albert, R. and Barabasi, A. L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1).

Albert, R., Jeong, H., and Barabasi, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406(6794):378–382.

Almaas, E. and Barabasi, A. (2004). Power laws in biological networks. q-bio.

Biskupski, B., Dowling, J., and Sacha, J. (2007). Properties and mechanisms of self-organizing manet and p2p systems. ACM Trans. Auton. Adapt. Syst., 2(1).

Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. (2000). Graph structure in the web. Computer Networks, 33(1):309–320.

Crucitti, P. and Latora, V. (2001). Efficient behavior of small-world networks. Physical Review Letters, 87(19):198701+.

Crucitti, P., Latora, V., Marchiori, M., and Rapisarda, A. (2004). Error and attack tolerance of complex networks. Physica A: Statistical Mechanics and its Applications, 340:Pages 388–394.

Dall’Asta, L., Barrat, A., Barthelemy, M., and Vespignani, A. (2006). Vulnerability of weighted networks. Theory and Experiment, 2006:04006.

Dodds, P. S., Muhamad, R., and Watts, D. J. (2003). An experimental study of search in global social networks. Science, 301(5634):827–829.

Erdős, P. and Rényi, A. (1959). On random graphs. Publicationes Mathematicae Debrecen, 6:290–297.

Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17–61.

Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). On power-law relationships of the internet topology. In In SIGCOMM, pages 251–262.

Holl, J. and H, M. S. (2003). An assessment of preferential attachment as a mechanism for human sexual network formation.

Klemm, K. and Eguíluz, V. (2002). Growing scale-free networks with small world behavior. Phys Rev E, (65).

Latora, V. and Marchiori, M. (2002). Economic small-world behavior in weighted networks.

Lua, K., Crowcroft, J., Pias, M., Sharma, R., and Lim, S. (2005). A survey and comparison of peer-to-peer overlay network schemes. Communications Surveys & Tutorials, IEEE, pages 72–93.

Newman, M. E. J. (2003). The structure and function of complex networks.

Stephenson (1989). Rethinking centrality: Methods and applications. Social Networks, 11:1–37.

Vega-Redondo, F. (2007). Complex Social Network. Cambridge University Press.

Wasserman, S., Faust, K., and Iacobucci, D. (1994). Social Network Analysis : Methods and Applications (Structural Analysis in the Social Sciences). Cambridge University Press.

Watts, D. J. (2003). Small Worlds : The Dynamics of Networks between Order and Randomness (Princeton Studies in Complexity). Princeton University Press.

Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ’small-world’ networks. Nature, 393(6684):440–442.

Wuchty, S. (2003). Small worlds in rna structures. Nucl. Acids Res., 31:1108–1117.