Research On Clustering And Identifying Of Mobile Call Network Nodes Based On Graph Mining

With the development of science and technology, mobile communication has become an indispensable way to interact in daily life. Mobile operators, as call service provider, have accumulated a large number of user call data records. We can build mobile call graph with call data records. Graph could describe the subjects and interactive relationships between subjects naturally. Clusters are the ubiquitous property, reflecting the group pattern of nodes. By clustering, we can effectively identify the nodes with same structure, and understand the behavior patterns of the node deeply. There are different kinds of important nodes. Some have a great influence, or live in a key location during the process of information transmission. The identification of important nodes could help find information diffusion patterns, and accelerate the diffusion of information.Clustering and identifying of important nodes based on graph mining have always been a hot topic in large-scale network data analysis. Many researchers have done a lot of work. The status of the arts researches mostly focus on the statistical analysis of mobile call graph. In this thesis, we utilized the concept of betweenness and design to achieve the clustering and important nodes identification of mobile call graph. The contents of study include the following aspects:1. Improve the undirected graph clustering algorithm, and successfully extend to directed case. The improved algorithm could process directional edge and weighted graph;2. According to the cutting points, propose a method to split the cutting points in weighted directed graph, which can effectively discover different types of clusters.3. Based on the clustering results, design to achieve the identification of inter-cluster core nodes and key node in information dissemination path.4. According to the identifying result, design to achieve the mining of clusters based on information flow model in mobile call graph. In this thesis, we utilized "SocialEvolution" and "Friends and Family" datasets, collected by MIT Human Dynamics Laboratory, to verify the correctness and efficiency of the algorithms. The results of study are helpful for telecom operators to precisely divide users, and design special user incentives, as well as combine with recommendation system to do business promotion.