Computational Aspects of Analyzing Social Network Dynamics
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 2268-2272.
Abstract
Motivated by applications such as the spread of epidemics and the propagation of influence in social networks, we propose a formal model for analyzing the dynamics of such networks. Our model is a stochastic version of discrete dynamical systems. Using this model, we formulate and study the computational complexity of two fundamental problems (called reachability and predecessor existence problems) which arise in the context of social networks. We also point out the implications of our results on other computational models such as Hopfield networks, communicating finite state machines and systolic arrays.
@inproceedings{ijcai2007p365,
title = {Computational Aspects of Analyzing Social Network Dynamics},
author = {Barrett, Christopher L. and III, Harry B. Hunt and Marathe, Madhav V. and Ravi, S. S. and Rosenkrantz, Daniel J. and Stearns, Richard Edwin and Thakur, Mayur},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {2268--2272},
year = {2007},
url = {https://ijcai.org/proceedings/2007/365},
}
TY - CPAPER TI - Computational Aspects of Analyzing Social Network Dynamics AU - Barrett, Christopher L. AU - III, Harry B. Hunt AU - Marathe, Madhav V. AU - Ravi, S. S. AU - Rosenkrantz, Daniel J. AU - Stearns, Richard Edwin AU - Thakur, Mayur T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 2268 EP - 2272 UR - https://ijcai.org/proceedings/2007/365 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
