| 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.
|
