2005-26: Critical Groups in Dynamic Social Networks

DIMACS TR: 2005-26

Critical Groups in Dynamic Social Networks

Authors: Tanya Y Berger-Wolf and Jared Saia

ABSTRACT
We address the issue of fragility of a network of interactions, such as a social network, in a dynamic setting. We propose a new mathematical and computational framework that allows analysis of dynamic social networks addressing the time component explicitly. In this framework, we pose the question of finding a critical set of groups at various times whose lack of existence would leave no persistent social structure in the network. We formulate this question in terms of a graph optimization problem, prove that it is NP-hard, and provide a polynomial time algorithm for one important special case.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-26.ps.gz

DIMACS Home Page