Data originating from many different real-world domains can be represented meaningfully as interaction networks. Examples abound, ranging
from gene expression networks to social networks, and from the World Wide
Web to protein-protein interaction networks. The study of these
complex networks can result in the discovery of meaningful patterns and can
potentially afford insight into the structure, properties and
behavior of these networks. Hence, there is a need to design suitable algorithms to extract or infer meaningful information from these networks. However, the
challenges involved are daunting.
First, most of these real-world networks have specific topological
constraints that make the task of extracting useful
patterns using traditional data mining techniques difficult. Additionally,
these networks can be noisy (containing unreliable interactions),
which makes the process of knowledge discovery difficult. Second, these
networks are usually dynamic in nature. Identifying the portions of the
network that are changing, characterizing and modeling the evolution, and
inferring or predicting future trends are critical challenges that need
to be addressed in the context of understanding the evolutionary behavior of
such networks.
To address these challenges, we propose a framework of algorithms
designed to detect, analyze and reason about the structure, behavior and evolution of real-world interaction networks. The proposed
framework can be divided into three components:
1. A static analysis component where we propose efficient,
noise-resistant algorithms taking advantage of specific topological
features of these networks to extract useful functional modules and motifs from
interaction graphs.
2. An event detection component where we propose algorithms to
detect and characterize critical events and behavior for evolving
interaction graphs
3. A temporal reasoning component where we propose approaches wherein one
can make useful inferences on events, communities, individuals and their
interactions over time.
For each component, we propose either new algorithms, or suggest ways
to apply existing techniques in a previously-unused manner. Where
appropriate, we compare against traditional or accepted standards.
We evaluate the proposed framework on real datasets drawn from clinical,
biological and social domains.