* Faculty       * Staff       * Contact       * Institute Directory
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Algorithms for Discovering Hidden Groups in Communications

By Jeffrey Baumes
Advisor: Mark Goldberg
August 25, 2006

Technologies such as email, chatrooms and web logs allow individuals to communicate in a number of new ways, and new forms of communications are continually appearing. As vast amounts of digital communication data are collected, communication logs may potentially contain millions of pieces of information, which must be pre-processed in order to present an intelligence analyst with a set of communication groups. We call these groups "hidden groups" since their membership is not explicit, but is implicitly implied in their communication structure. We present a strategy for discovering hidden groups within a communication network; through searching for significant correlations, which may be temporal or structural. The temporal algorithms discover hidden groups connected over any range of time in the dataset. We find that a temporal hidden group must choose between two options: trust individuals outside the group to relay information, or else impose a structure upon themselves which is more easily detected by our algorithms. For structural hidden groups, we propose a novel approach to the problem of graph clustering, where we allow clusters to overlap by letting them extend to local optima with respect to a generic density metric. We compare and contrast different algorithms for finding clusters in this way, and show that a particular algorithm combination, performs well on both simulated and real-world data. The software system SIGHTS incorporates these algorithms into a single framework, along with associated visualizations.

* Return to main PhD Theses page