Understanding the structure of power law networks

ABSTRACT

The degree distribution of scale-free networks follow power laws. There continues to be disagreement, however, as to what additional properties these networks share. A wide range of techniques useful as aids in understanding common structure as well as in differentiating between elements of this class of networks are explored. First, the utility of a polar coordinate plot for power law distributions is explained. Second, computational experience with two procedures to uncover shortest paths in scale-free networks based solely on locally available data is provided. Next, a tabu search is developed to find high quality solutions for two bi-objective models. For specific objective weights, networks whose degree distributions follow a power law are shown to arise. Lastly, links between the clustering coefficient distribution and modularity are described. Computational experiments supporting the connection between the first nontrivial eigenvalue of a Laplacian matrix and network synchrony are conducted.

REFERENCES

• 1: Albert, R. and A.-L. Barabási, "Statistical Mechanics of Complex Networks," Rev. Modern Physics, 74:42--47 (2002).
• 2: Atay, F. M. and J. Jost, "Delays, Connection Topology, and Synchronization of Coupled Chaotic Maps," Physical Review Ltrs., 92(14):144101(4) (2004).
• 3: Atay, F. M., T. Biyikoglu and J. Jost, "Synchronization of Networks with Prescribed Degree Distributions," arXiv:nlin.AO/0407024 v2, May (2005).
• 4: Barabási, A.-L., Linked: The New Science of Networks, Perseus, Cambridge, MA, 2002
• 5: Barabási, A.-L., Z. Dezsó, E. Ravasz, S-H. Yook, and Z. Oltvai, "Scale-free and hierarchical structures in complex networks," to appear in Sitges Proceedings on Complex Networks, (2004).
• 6: Barahona, M. and L. M. Pecora, "Synchronization in Small-World Networks," Physical Review Letters, 89, no. 5 (2002).
• 7: Dorogovtsev, S. N. and J. F. F. Mendes, "Evolution of Networks," Advances in Phys., 51:1079--1187 (2002).
• 8: Ferrer-Cancho, R. and R. V. Solé, "Optimization in Complex Networks," Preprint 0111222 (2001) available from http://arxiv.org/abs/cond-mat/.
• 9: Fiedler, M., "Algebraic connectivity of graphs," Czech. Math. Journal, 23, 298--305 (1973).
• 10: Glover, F. "Tabu Search, Part I," ORSA J. on Computing, 1:190--206 (1989).
• 11: Fred Glover, Tabu Search, Kluwer Boston, Inc., 1998
• 12: Gong, P. and C. Van Leeuwen, "Emergence of Scale-Free Network Structure with Chaotic Units," Preprint, Laboratory for Perceptual Dynamics, Japan (2002).
• 13: Holme, P. and B. J. Kim "Growing Scale-free Networks with Tunable Clustering," Physical Review E, 65 (026107) (2002).
• 14: Kincaid, R. K., M. J. Holroyd, and N. Alexandrov "Synchrony and Networks," em NASA TM, (2006).
• 15: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 16: Li, L., D. Alderson, R. Tanaka, J. C. Doyle and W. Willinger, "Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications," Preprint 0501169v1 (2005) available at http://arXiv:cond-mat/.
• 17: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 18: Manna, S. S. and A. Kabakcioglu, "Scale-free network on Euclidean space optimized by rewiring of links," J. Phys. A: Math. Gen., 36:279--285 (2003).
• 19: Mathias, N. and V. Gopal, "Small-worlds: How and why," Phys. Rev. E,63:1--20 (2001).
• 20: Milgram, S., Psych. Today, 2:60 (1967).
• 21: Newman, M. E. J., "The Structure and Function of Complex Networks," SIAM Review, 45:167--256 (2003).
• 22: Newman, M. E. J., "Modularity and community structure in networks," PNAS, 103, No. 3, 8577--8582 (2006).
• 23: Ricard V. Solé , Ramon Ferrer-Cancho , Jose M. Montoya , Sergi Valverde, Selection, tinkering, and emergence in complex networks, Complexity, v.8 n.1, p.20-33, September 2002 [doi>10.1002/cplx.10055]
• 24: Strogatz, S. H., "Exploring Complex Networks," Nature, 410:268--276, March (2001).
• 25: Tadić, B., "Exploring Complex Graphs by Random Walks," in Modeling Complex Systems, P. L. Garrido and J. Marro (eds.), AIP Conference Proceedings, 661, 24 (2002).
• 26: Wang, W-X., B. Hu, B-H. Wang, and G. Yan arXiv: cond-mat/0505419 v1, May (2005).
• 27: Wu, C. W., "Perturbation of Coupling Matrices and Its Effect on the Synchronizability in Arrays of Coupled Chaotic Systems," Preprint 0307052 (2006) available at http://arXiv/pdf/nlin.CD/.

INDEX TERMS

Keywords:
complex system, degree distribution, networks, optimization, scale-free, tabu search