The week's pick
Reseach Article
Is Power Law the Universal Law for Large Real Graph: Interneth
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 83 - Number 6 |
| Year of Publication: 2013 |
| Authors: Pathik Sharma |
10.5120/14449-2707
|
Pathik Sharma . Is Power Law the Universal Law for Large Real Graph: Interneth. International Journal of Computer Applications. 83, 6 ( December 2013), 1-6. DOI=10.5120/14449-2707
Abstract
Power laws are observed in many large networks such as Internet, WWW, automobile networks, etc. First half of the paper captures some of the instance of internet over a period of time. Now after comparing topologies of Internet with power laws, it cannot be ignored by saying it a mere coincidence. So, real networks (Internet) thus follows power law. Determining the behavior of such a large network has always been curiosity. Owing to that, different parameters such as number of nodes and edges, average neighborhood size, etc. has been derived to better predict behavior. Second half of paper discuss about generating topologies nearly same as realistic graphs. Also the generated topology must adhere to power laws. Some factors are imposed on topologies to get finer results. To better predict the behavior of topologies some more parameters such as diameter, Incremental Growth and Preferential Connectivity are considered. At last some extension of proposed method is discussed along with its possible application.
References
- Medina, Alberto, Ibrahim Matta, and John Byers. "On the origin of power laws in Internet topologies. " ACM SIGCOMM computer communication review 30. 2 (2000): 18-28.
- Faloutsos, Michalis, Petros Faloutsos, and Christos Faloutsos. "On power-law relationships of the internet topology. " ACM SIGCOMM Computer Communication Review. Vol. 29. No. 4. ACM, 1999.
- Siganos, Georgos, et al. "Power laws and the AS-level internet topology. " IEEE/ACM Transactions on Networking (TON) 11. 4 (2003): 514-524.
- Palmer, Christopher R. , and J. Gregory Steffan. "Generating network topologies that obey power laws. " Global Telecommunications Conference, 2000. GLOBECOM'00. IEEE. Vol. 1. IEEE, 2000.
- Adamic, Lada A. , and Bernardo A. Huberman. "Power-law distribution of the world wide web. " Science 287. 5461 (2000): 2115-2115.
- Newman, Mark EJ. "Power laws, Pareto distributions and Zipf's law. " Contemporary physics 46. 5 (2005): 323-351.
- Mahanti, Aniket, et al. "A tale of the tails: Power-laws in internet measurements. " Network, IEEE 27. 1 (2013): 59-64.
- Winick, Jared, and Sugih Jamin. Inet-3. 0: Internet topology generator. Technical Report CSE-TR-456-02, University of Michigan, 2002.
- Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks. " science 286. 5439 (1999): 509-512.
- Mandelbrot, Benoit B. The fractal geometry of nature. Macmillan, 1983.
- Faloutsos, Christos, and Ibrahim Kamel. "Beyond uniformity and independence: Analysis of R-trees using the concept of fractal dimension. " Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. ACM, 1994.
- Clauset, Aaron, Cosma Rohilla Shalizi, and Mark EJ Newman. "Power-law distributions in empirical data. " SIAM review 51. 4 (2009): 661-703.
- Mitzenmacher, Michael. "A brief history of generative models for power law and lognormal distributions. " Internet mathematics 1. 2 (2004): 226-251.
- Mislove, Alan, et al. "Measurement and analysis of online social networks. " Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM, 2007.
- Paxson, Vern, and Sally Floyd. "Why we don't know how to simulate the Internet. " Proceedings of the 29th conference on Winter simulation. IEEE Computer Society, 1997.
- Pansiot, Jean-Jacques, and Dominique Grad. "On routes and multicast trees in the Internet. " ACM SIGCOMM Computer Communication Review 28. 1 (1998): 41-50.
- Govindan, Ramesh, and Anoop Reddy. "An analysis of Internet inter-domain topology and route stability. " INFOCOM'97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE. Vol. 2. IEEE, 1997.
- Zegura, Ellen W. , Kenneth L. Calvert, and Michael J. Donahoo. "A quantitative comparison of graph-based models for Internet topology. " IEEE/ACM Transactions on Networking (TON) 5. 6 (1997): 770-783.
- Kleinberg, Jon M. "Authoritative sources in a hyperlinked environment. " Journal of the ACM (JACM) 46. 5 (1999): 604-632.
- Cvetkovic, Dragos M. , Michael Doob, and Horst Sachs. Spectra of graphs: Theory and application. Vol. 413. New York: Academic press, 1980.
Index Terms
Keywords