Mobile call graphs: beyond power-law and lognormal distributions

ABSTRACT

We analyze a massive social network, gathered from the records of a large mobile phone operator, with more than a million users and tens of millions of calls. We examine the distributions of the number of phone calls per customer; the total talk minutes per customer; and the distinct number of calling partners per customer. We find that these distributions are skewed, and that they significantly deviate from what would be expected by power-law and lognormal distributions.

To analyze our observed distributions (of number of calls, distinct call partners, and total talk time), we propose PowerTrack , a method which fits a lesser known but more suitable distribution, namely the Double Pareto LogNormal (DPLN) distribution, to our data and track its parameters over time. Using PowerTrack , we find that our graph changes over time in a way consistent with a generative process that naturally results in the DPLN distributions we observe. Furthermore, we show that this generative process lends itself to a natural and appealing social wealth interpretation in the context of social networks such as ours. We discuss the application of those results to our model and to forecasting.

REFERENCES

• 1: Lada A. Adamic , Bernardo A. Huberman, The Web's hidden order, Communications of the ACM, v.44 n.9, p.55-60, Sept. 2001 [doi>10.1145/383694.383707]
• 2: L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley. Classes of small-world networks. Proceedings of the National Academy of Sciences, 97(21):11149--11152, 2000.
• 3: A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 4: Zhiqiang Bi , Christos Faloutsos , Flip Korn, The "DGX" distribution for mining massive, skewed data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.17-26, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502521]
• 5: P. Boldi, B. Codenotti, M. Santini, and S. Vigna. Structural properties of the African Web. In International World Wide Web Conference, New York, NY, 2002. ACM Press.
• 6: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 7: A. Clauset. Power law distributions in empirical data. http://www.santafe.edu/~aaronc/powerlaws/
• 8: A. Clauset, C. R. Shalizi, and M. E. J. Newman. Power-law distributions in empirical data. ArXiv e-print 0706.1062v1, 2007.
• 9: Corinna Cortes , Daryl Pregibon , Chris Volinsky, Communities of Interest, Proceedings of the 4th International Conference on Advances in Intelligent Data Analysis, p.105-114, September 13-15, 2001
• 10: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 11: R. Govindan and H. Tangmunarunkit. Heuristics for Internet map discovery. In IEEE INFOCOM, pages 1371--1380, Los Alamitos, CA, March 2000. IEEE Computer Society Press.
• 12: J.-P. Onnela, J. Saramaäki, J. Hyvöven, G. Szabó, M. Argollo de Menezes, K. Kaski, and A.-L. Barabási. Structure and Tie Strengths in Mobile Communication Networks. New Journal of Physics, 9, 2007.
• 13: S. Keshav, Why cell phones will dominate the future internet, ACM SIGCOMM Computer Communication Review, v.35 n.2, April 2005 [doi>10.1145/1064413.1064425]
• 14: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 15: M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, 1(2):226--251.
• 16: M. Mitzenmacher. Dynamic Models for File Sizes and Double Pareto Distributions. Internet Mathematics, 1(3):305--334, 2004.
• 17: Amit A. Nanavati , Siva Gurumurthy , Gautam Das , Dipanjan Chakraborty , Koustuv Dasgupta , Sougata Mukherjea , Anupam Joshi, On the structural properties of massive telecom call graphs: findings and implications, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183678]
• 18: M. E. J. Newman. Power laws, pareto distributions and Zipf's law. Contemporary Physics, 46:323--351, 2005.
• 19: M. E. J. Newman. Power laws, pareto distributions and Zipf's law. Contemporary Physics, 46:323--351, 2005.
• 20: V. Pareto. Oeuvres Completes. Droz, Geneva, 1896.
• 21: D. M. Pennock, G. W. Flake, S. Lawrence, E. J. Glover, and C. L. Giles. Winners don't take all: Characterizing the competition for links on the Web. Proceedings of the National Academy of Sciences, 99(8):5207--5211, 2002.
• 22: S. Redner. How popular is your paper? an empirical study of the citation distribution. The European Physics Journal B, 4:131--134, 1998.
• 23: W. Reed and M. Jorgensen. The double pareto-lognormal distribution - a new parametric model for size distribution. Communications in Statistics -Theory and Methods, 33(8):1733--1753, 2004.
• 24: R.Gibrat. inégalités économiques. Librarie du Recuil Sirey, 1931.
• 25: G. Szabo and A.-L. Barabasi. Network effects in service usage. ArXiv e-prints physics/0611177, November 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
DPLN, distribution, generative process, power laws