Modelling and Mining of Networked Information Spaces

Project Title: Structural analysis of dynamic communication graphs
Participants: Dr. Bill Aiello, Dr. Jeannette Janssen, Dr. Evangelos Milios, John Healy
Project Description: The community structure inherently present in social networks is typically of a hierarchical nature, where individuals belong to communities of varying levels of coherence or density. This notion is borne out in graph theoretic terms by the concept of "core". A core is a maximal subgraph for which a certain node-specific condition holds. The oldest version is the k-core, which is the maximum subgraph where all nodes have degree at least k. Cores can be computed efficiently, and they exhibit an inherent hierarchical structure. The goal of this project is to use to the notion of k-core to map the hierarchical structure in a dynamic social network, and study how its structure changes over time. The aim is to track the development of existing communities over time, and spot the formation of new aliances while filtering out chance encounters. Another objective is to model a real dynamic graph in terms of one of several generative models by analyzing the graph's hierarchical k-core based representation. Ultimately, these efforts will lead to a characterization of "normal" patterns in a dynamic graphs. Once normal behaviour has been quantified, an automatic monitoring system can be developed which will detect anomalous patterns.