3rd International ICST Conference on COMmunication System SoftWAre and MiddlewaRE

Research Article

Extracting Dense Communities from Telecom Call Graphs

  • @INPROCEEDINGS{10.1109/COMSWA.2008.4554383,
        author={Vinayaka Pandit and Natwar Modani and Sougata Mukherjea and Amit A. Nanavati and Sambuddha Roy and Amit Agarwal},
        title={Extracting Dense Communities from Telecom Call Graphs},
        proceedings={3rd International ICST Conference on COMmunication System SoftWAre and MiddlewaRE},
  • Vinayaka Pandit
    Natwar Modani
    Sougata Mukherjea
    Amit A. Nanavati
    Sambuddha Roy
    Amit Agarwal
    Year: 2008
    Extracting Dense Communities from Telecom Call Graphs
    DOI: 10.1109/COMSWA.2008.4554383
Vinayaka Pandit1,*, Natwar Modani1, Sougata Mukherjea1, Amit A. Nanavati1, Sambuddha Roy1, Amit Agarwal2,*
  • 1: IBM India Research Laboratory New Delhi, India
  • 2: Department of Statistics and Operations Research University of North Carolina Chapel Hill, North Carolina
*Contact email: pvinayak@in.ibm.com, aagarwal@email.unc.edu


Social networks refer to structures made of nodes that represent people or other entities embedded in a social context, and whose edges represent interaction between entities. Typical examples of social networks are collaboration networks in a research community, networks arising out of interaction between colleagues of large organization etc. Social networks are highly dynamic objects that evolve quickly over time with addition and deletion of nodes and edges. Understanding the evolution of a social network is helpful in inferring trends and patterns of social contacts in a particular social context. In this paper, we consider social networks that are derived from Telephone Call Records, i.e, graphs in which the individual phone numbers (and hence its users) are the nodes and the edges correspond to a telephonic contact between the two nodes they connect. We study the problem of extracting dense communities from such Telecom Call Graphs. The problem studied here is set in the context of a larger project. We motivate the problem studied by describing the context in which it is set. Our analysis is based on suitable algorithmic engineering of an approximation algorithm for the densest subgraph problem by Charikar. We present empirical results on massive graphs with millions of nodes and edges. We also discuss many open problems that are important in the context of analysing telecom call graphs.