On the structural properties of massive telecom call graphs: findings and implications

ABSTRACT

With ever growing competition in telecommunications markets, operators have to increasingly rely on business intelligence to offer the right incentives to their customers. Toward this end, existing approaches have almost solely focussed on the individual behaviour of customers. Call graphs, that is, graphs induced by people calling each other, can allow telecom operators to better understand the interaction behaviour of their customers, and potentially provide major insights for designing effective incentives.In this paper, we use the Call Detail Records of a mobile operator from four geographically disparate regions to construct call graphs, and analyse their structural properties. Our findings provide business insights and help devise strategies for Mobile Telecom operators. Another goal of this paper is to identify the shape of such graphs. In order to do so, we extend the well-known reachability analysis approach with some of our own techniques to reveal the shape of such massive graphs. Based on our analysis, we introduce the Treasure-Hunt model to describe the shape of mobile call graphs. The proposed techniques are general enough for analysing any large graph. Finally, how well the proposed model captures the shape of other mobile call graphs needs to be the subject of future studies.

REFERENCES

• 1: Pajek: Program for large network analysis. http://vlado.fmf.uni-lj.si/pub/networks/pajek.
• 2: J. Abello , P. Pardalos , M. G. C. Resende, On maximum clique problems in very large graphs, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 3: Barabasi, A. Emergence of scaling in complex networks. Handbook of Graphs and Networks, S. Bornholdt and H. Schuster (Editors) (2003).
• 4: Barabasi, A.-L., and Albert, R. Emergence of scaling in random networks. Science 286 (October 1999), 509--512.
• 5: Bollobás, B., and Riordan, O. Robustness and vulnerability of scale-free random graphs. Internet Mathematics 1 (2003), 1--35.
• 6: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 7: 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
• 8: Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y., and Shir, E. Medusa - new model of internet topology using k-shell decomposition, 2006. http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cond-mat/0601240.
• 9: Chan, W.-H. A., and Yao, K. X. A novel evolutionary data mining algorithm with applications to churn prediction. IEEE Transaction on Evolutionary Computation 7, 6 (Dec 2003), 532--545.
• 10: Donato, D., Lauraa, L., Leonardi, S., and Millozzi, S. Large scale properties of the webgraph. The European Physical Journal B 38 (2004), 239--243.
• 11: Donato, D., and Leonardi, S. Mining the inner structure of the web graph. In Eighth International Workshop on the Web and Databases (2005).
• 12: Euler, T. Churn prediction in telecommunications using miningmart. In Proceedings of the Workshop on Data Mining and Business (DMBiz) (2005). citeseer.ist.psu.edu/euler05churn.html.
• 13: 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
• 14: Haveliwala, T. H. Efficient computation of pagerank. Technical report, Stanford University, 1999.
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 16: Ravi Kumar , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Structure and evolution of blogspace, Communications of the ACM, v.47 n.12, December 2004 [doi>10.1145/1035134.1035162]
• 17: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceeding of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 18: Newman, M. E. J. Assortative mixing in networks. Physical Review Letters 89 (2002), 208701.
• 19: Newman, M. E. J. Mixing patterns in networks. Physical Review E 67 (2003), 026126.
• 20: Newman, M. E. J. The structure and function of complex networks. SIAM Review 45 (2003), 167.
• 21: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 22: Siganos, G., Tauro, S. L., and Faloutsos, M. Jellyfish: A conceptual model for the as internet topology. Journal of Communications and Networks. Under review.
• 23: Watts, D. J., and Strogatz, S. H. Collective dynamics of small-world networks. Nature 393 (1998), 440--442.
• 24: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
graph analysis