Scalable Solutions for Social Network Analysis

A telecom operator can get a lot of high quality intelligence by studying the social network of its subscribers. One way to generate such a social network is to study the calls between the subscribers. Social networks generated from telecom networks can consist of millions of subscribers and the majority of the current social network analysis algorithms are too slow to analyze large networks. This master's thesis' objective is to find a more scalable solution to analyze social networks. The work was divided into three steps; a survey of the existing solutions and algorithms, a pre-study to verify limitations of existing solutions and test some ideas and from the result of the pre-study and the survey a prototype was planned and implemented. From the pre-study it was clear that the current solutions both took too long and used too much memory to be possible to use on a large social network. A number of algorithms were tested and from those a few was chosen to be implemented in the prototype. To help with the memory and time consumption the solution was also parallelized by using a partitioning algorithm to divide the graph into separate pieces on which each algorithm could run locally.The partitioning algorithm failed to scale well due to an internal modification of the partitioning scheme to adapt the partitioning to social graphs and simplify the parallelization. All but one algorithm scaled well and they were considerably faster than the original algorithms