Community Identification, Evolution and Prediction in Dynamic Social Networks

  • Author / Creator
    Takaffoli, Mansoureh
  • Information networks that describe the relationship between individuals are called social networks and are usually modeled by a graph structure. Social network analysis is the study of these information networks which leads to uncovering patterns of interaction among the entities. Community mining provides a higher level of structure and offers greater understanding, but networks change over time. Their constituent communities change, and the elements of those communities change over time as well, i.e. they have fluctuating members and can grow and shrink over time. Examining how the structure of these networks and their communities changes over time provides insights into their evolution patterns, factors that trigger the changes, and ultimately predict the future structure of these networks. Furthermore, this prediction has many important applications, such as recommendation systems and customer targeting. In this PhD research dissertation, we provide a brief overview of the existing research in the area of dynamic social network analysis, and their limitations. Then, we present a framework, called MODEC, for modelling, detecting, and predicting the evolution of communities and individuals over time in a dynamic scenario. We introduce a new incremental community mining approach, in which communities in the current time are obtained based on the communities from the past time frame. Then, with the definition of the critical events and transitions, and applying our event analysis, the evolutions of communities are abstracted in order to see structure in the dynamic change over time. This higher level of analysis has a counterpart that deals with the fine grain changes in community members with relation to their communities or the global network. A community matching algorithm is also proposed to efficiently identify and track similar communities over time. We also define the concept of meta community which is a series of similar communities captured in different timeframes and detected by our matching algorithm. Furthermore, the events detected by the framework are supplemented by the extraction and investigation of the topics discovered for each community, and extensive experimental studies on real datasets, demonstrate the applicability, effectiveness, and soundness of our proposed framework. After analyzing the dynamic of social network, we predict the occurrence of different events and transition for communities. Our framework incorporates key features related to a community -- its structure, history, and influential members, and automatically detects the most predictive features for each event and transition. Our experiments on real world datasets confirm that the evolution of communities can be predicted with a very high accuracy, while we further observe that the most significant features vary for the predictability of each event and transition.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Doctor of Philosophy
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Zaiane, Osmar R
  • Examining committee members and their departments
    • Sander, Joerg (Computing Science)
    • Goebel, Randy (Computing Science)
    • Shiri, Ali (School of Library and Information Studies)