Award Abstract #0346341
SGER ACT: Locating Hidden Groups in Communication Networks

NSF Org:	DMS Division of Mathematical Sciences
Initial Amendment Date:	August 29, 2003
Latest Amendment Date:	October 1, 2004
Award Number:	0346341
Award Instrument:	Standard Grant
Program Manager:	Michael H. Steuerwalt DMS Division of Mathematical Sciences MPS Directorate for Mathematical & Physical Sciences
Start Date:	September 1, 2003
Expires:	January 31, 2005 (Estimated)
Awarded Amount to Date:	$57026
Investigator(s):	Malik Magdon-Ismail magdon@rpi.edu (Principal Investigator) William Wallace (Co-Principal Investigator) Mark Goldberg (Co-Principal Investigator)
Sponsor:	Rensselaer Polytechnic Institute 110 8TH ST Troy, NY 12180 518/276-6000
NSF Program(s):	OFFICE OF MULTIDISCIPLINARY AC
Field Application(s):	0000099 Other Applications NEC
Program Reference Code(s):	OTHR, 9237, 7276, 7243, 0000
Program Element Code(s):	1253

ABSTRACT

It is proposed to develop models and algorithms for identifying groups that camouflage their functioning in a large communication network. Since the communications of an aberrant group are often encrypted or unreliable, it is proposed to develop algorithms that use only communication intensities, and do not rely communication semantics. The results of this research can also be used for the early detection and monitoring of aberrant groups that may be planning/coordinating undesirable activities. Tools will be developed that provide a first defense against such activities and therefore have wider impact in national security and defense. The proposed work is distinguished from prior research in two ways. The first is that the brand-new problem of detecting the hidden group itself, using only communication data, will be studied. The most relevant work lies in the social network literature wherein it is assumed that the members of the aberrant group are already known and one studies, for example, how certain actions affect properties of the network such as its stability or communication potential. The second is that in order to accomplish the task, novel methodologies will be developed:

i. The communications will be modeled as a Hidden Markov Model (HMM). The state space corresponds to the group structure of the society, where a group is a collection of individuals with some commonality. The hidden (aberrant) group constitutes one of the groups that participates in the communications. The model of how the social groups evolve and communicate can be learned: given the prior communication behavior of the society, a HMM is calibrated to the prior behavior. If this HMM does not adequately explain the present behavior, but a HMM which incorporates a hidden group does, then one can determine the existence of the hidden group as well as its members.

ii. Combinatorial algorithms will be used to detect persistent hidden group communication structures as candidate initial hidden groups. Such structures include simple cycles, trees, cliques, stars and wheels. The results of such algorithms will be used as initial candidate hidden groups that can be fine-tuned using the HMM approach. The algorithms will be designed and tested on simulated test beds, as well as on real communication data such as newsgroups. While the primary goal is to develop tools for detecting hidden groups, the tools will also provide a vehicle for integrating education with the research. Models of evolving societies and hidden groups will be developed that will allow K-8 through high-schools to "test" their understanding of societal behavior by attempting to predict whether there is a hidden group, who the members are, and comparing their predictions with the automated "computer" predictions and the true answer. Such a model will be implemented at RPI on a web server and at the Junior Museum in Troy, NY. The goal of such demonstrations is to improve students' understanding of the behavior of communication networks and detection of anomalous behavior. In addition, this research will be incorporated into a research-oriented, interdisciplinary educational experience for students who otherwise might never be involved in such research. By conducting cross-disciplinary research involving mathematical, computer and social sciences, the pool of eligible research assistants will be broadened, which will significantly increase the possibility of identifying qualified candidates from underrepresented groups.

This award is supported jointly by the NSF and the Intelligence Community. The Approaches to Combat Terrorism Program in the Directorate for Mathematical and Physical Sciences supports new concepts in basic research and workforce development with the potential to contribute to national security.

Please report errors in award information by writing to: awardsearch@nsf.gov.