Influence Maximization in Large Scale Cellular Phone Social Networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering

FYT Presentation and Demonstration

Title: "Influence Maximization in Large Scale Cellular Phone Social Networks"

by

LI Maocheng, Michael

Efficient solutions to Influence Maximization Problem have
important and broad applications in both business settings and
policy making process of government. For instance, identifying
customers with higher potential of influencing others would
effectively bring more profits and save marketing costs for
companies.

Influence Maximization Problem is essentially to find a small subset of
nodes in a social network which have maximal network effort (spread of
influence). Previous researches show that this problem is NP-Complete and
propose greedy algorithms for approximation. However, further
improvements to the approximation algorithm are still needed.

In this work, we construct social networks from the cellular phone call
records collected in a city over the period of one year. We are the first
to utilize such sensitive information to build social networks of such
scale. By experiments, we show that exiting greedy algorithms suffer from
prohibitive overhead, while our pruning heuristic utilizes the unique
feature of cellular phone social networks and provides over 300 times
speed up and a feasible algorithm. In addition, we propose a more suitable
social network model to capture the dynamics of relationship between
individuals.


Date		:	12 May 2010

Time		:	1:30pm to 2:15pm

Venue		:	Rm 3416

Advisor		:	Prof. Lionel Ni

2nd Reader	:	Dr. Chen Lei