Chester Clinic

 

Wwwconference.org

WWW 2011 – Tutorial
March 28–April 1, 2011, Hyderabad, India
Tutorial: Game Theoretic Models for Social Network
Ramasuri Narayanam Electronic Commerce Laboratory IBM India Research Lab Dept. of Computer Science and Automation Indian Institute of Science, Bangalore, India ten, the individuals in the network exhibit strategic The existing methods and techniques for social network anal- ysis are inadequate to capture both the behavior (such asrationality and intelligence) of individuals and the strate- 2. They do not explicitly capture the dynamics of strate- gic interactions that occur among these individuals. Game gic interaction among the individual in the networks.
theory is a natural tool to overcome this inadequacy since Game theory [12, 13] is a natural tool to overcome these it provides rigorous mathematical models of strategic inter- fundamental problems, as it provides a rich suite of mathe- action among autonomous, intelligent, and rational agents.
matical models of strategic interaction among autonomous, Motivated by the above observation, this tutorial provides intelligent, and rational individuals (or players). Game the- the conceptual underpinnings of the use of game theoretic oretic models are thus best suited to capture the strategic models in social network analysis. In the first part of the tu- nature of individuals making up a social network. Game torial, we provide rigorous foundations of relevant concepts theoretic models are also complementary to the current SNA in game theory and social network analysis.
approaches and hence they add a new dimension to the area ond part of the tutorial, we present a comprehensive study of SNA. Recently there have been several efforts in following of four contemporary and pertinent problems in social net- a game theoretic approach to social network modeling [18, works: social network formation, determining in influential 7, 5, 10, 15, 6, 11, 9, 2, 1, 17, 16].
individuals for viral marketing, query incentive networks, In our view, game theoretic models are appropriate for and community detection.
social network analysis from two perspectives:(a) Game theoretic models are very natural for several prob- Categories and Subject Descriptors
lems in social network analysis. A few such problems include F.2.2 [Analysis of Algorithms and Problem Complex-
social network formation [7, 5, 10, 15], social network mon- ity]: Nonnumerical Algorithms and Problems
etization [6], and bargaining on networks [11].
(b) Game theoretic models are useful as a tool to solve cer-tain interesting problems in social network analysis. This leads to not only a deeper understanding of those problems Economics, Theory but also efficient algorithms. A few examples of this kindinclude query incentive networks [9, 2], discovering commu- nities in networks [1, 17], determining influential individualsfor viral marketing [16], etc.
Social networks, game theory, viral marketing, network for-mation, query incentive networks, community detection CONTENT OF THE TUTORIAL
Here we present a brief description of the material and the results that we discuss in this tutorial.
Social network analysis (SNA) [19] comprises a well devel- oped suite of measures and metrics based on techniques such Social Network Analysis: A Quick Primer
as graph theory, spectral theory, optimization theory. Allthis machinery in SNA is useful to measure the structural First, we present a quick primer on social network analysis and statistical properties of social networks. In fact, gen- from Easley and Kleinberg [4]. We define important metrics erative models can reproduce networks with similar/same for social network analysis, prominent approaches for social structural properties. However, the current SNA approaches network analysis, and list a few benchmark problems.
are inadequate for the following reasons: Foundational Concepts in Game Theory
1. They do not satisfactorily capture the behavior of the Here we first present the basic concepts from both non- individuals in social networks. For example, very of- cooperative game theory and cooperative game theory. Ma-jority of this content is covered from Myerson [12]. We then Copyright is held by the author/owner(s).
present the foundational principles of mechanism design the- WWW 2011, March 28–April 1, 2011, Hyderabad, India.
ory from Narahari, Garg, Ramasuri, and Hastagiri [13].
WWW 2011 – Tutorial
March 28–April 1, 2011, Hyderabad, India
Social Network Formation
cial network analysis. We then motivate the need for a game The behavior of networks is driven by the actions of a theoretic approach to community detection and present two large number of autonomous individuals, each motivated by game theoretic models for community detection Chen, Liu, self-interest and individual objectives. As a consequence of Sun, and Wang [1] and Ramasuri and Narahari [17].
this, the global performance of such networks, which arethe equilibrium outcomes of decentralized strategic interac- tions, can be worse than that of a network that is enforced [1] W. Chen, Z. Liu, X. Sun, and Y. Wang. A game by a central authority. In the literature, networks that are theoretic framework to identify overlapping enforced by a central authority are known as efficient net- communities in social networks. DMKD, 21:224-240, works. Understanding the compatibility between the equi- librium networks and efficient networks is the primary focus [2] D. Dikshit and Y. Narahari. Truthful and Quality of research in network formation. Most of the results that we Conscious Query Incentive Networks. In Workshop on cover in this context are primarily from Jackson [7], Goyal Internet and Network Economics (WINE), 2009.
[5], Kleinberg, Suri, Tardos, and Wexler [10], and Ramasuri [3] P. Domingos and M. Richardson. Mining the network and Narahari [15].
value of customers. In ACM SIGKDD, 2001.
Discovering Influential Individuals for Vi-
[4] D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World.
Cambridge University Press, Cambridge, UK, 2010.
Viral Marketing is based on the conceptual framework of [5] S. Goyal. Connections: An Introduction to the diffusion of information. In this context, given a integer Economics of Networks. Princeton University Press, value k, it is very challenging to determine top-k influential Princeton and Oxford, 2007.
individuals to maximize the volume of information cascade.
Formally, we define an objective function σ(.) as follows. We [6] J.D. Hartline, V.S. Mirrokni, M. Sundararajan.
note that an individual is active if he/she adopts the product Optimal marketing strategies over social networks. In or technology. If S is the set of initially active nodes, then σ(S) is the expected number of active nodes at the end of the [7] M. O. Jackson. Social and Economic Networks.
diffusion process. For a given constant k, the top-k nodes Princeton University Press, 2008.
problem seeks to find a subset of nodes S of cardinality [8] D. Kempe, J. Kleinberg, and E. Tardos. Maximizing k that maximizes the value of σ(S). In this setting, we the spread of influence through a social network. In first cover certain fundamental results from Domingos and ACM SIGKDD, 2003.
Richardson [3], Kempe, Kleinberg, and Tardos [8]. Then [9] J.M. Kleinberg and P. Raghavan. Query Incentive we present a game theoretic approach to address the top-k Networks. In IEEE FOCS, pages 132-141, 2005.
nodes problem and we present a few results from Ramasuri [10] J. Kleinberg, S. Suri, E. Tardos, and T. Wexler.
and Narahari [16].
Strategic network formation with structural holes. InACM EC, pages 284-293, 2008.
Query Incentive Networks
[11] J.M. Kleinberg and E. Tardos. Balanced outcomes in We consider scenarios where a person in a social network social exchange networks. In STOC, 2008.
is seeking some information from the social network and the [12] R.B. Myerson. Game Theory: Analysis of Conflict. other connected individuals forward the query down in the Harvard University Press, 1997.
network as well as report back the answer, if any. Since ev- [13] Y. Narahari, Dinesh Garg, Ramasuri Narayanam, ery individual is an intelligent and rational agent and since Hastagiri Prakash. Game Theoretic Problems in forwarding the query (and then reporting back the answer) Network Economics and Mechanism Design Solutions. requires a certain amount of effort on her part, she may not In Series: Advance Information & Knowledge be willing to do so. While offering an appropriate incen- Processing (AIKP), Springer Verlag, London, 2009.
tive to the intermediate nodes will increase the total reward [14] Prabhakar Raghavan and Jon Kleinberg. Query which must be offered by the person posing the query, it Incentive Networks. In IEEE FOCS, 2005.
will also increase the exposure of the query. This concept [15] Ramasuri Narayanam and Y. Narahari. Topologies of was captured by the model of Raghavan and Kleinberg [14] Strategically Formed Social Networks Based on a who called these query incentive networks. In the tutorial, Generic Value Function - Allocation Rule Model. To we will bring out the role of game theory and mechanism appear in Social Networks (Elsevier), 2011.
design in the design of incentives in such networks [14, 2].
[16] Ramasuri Narayanam and Y. Narahari. A Shapley Community Detection in Social Networks
Value based Approach to Discover Influential Nodes inSocial Networks. In IEEE TASE, 8(1):130-147, 2011.
A community structure in a network is a division of net- [17] Ramasuri Narayanam and Y. Narahari. Nash Stable work nodes into groups within which the network connec- Partitioning of Graphs with Application to Community tions are dense, but between which the connections are sparse.
Detection in Social Networks. Under Review, 2010.
Detecting communities in networks helps to understand theunderlying characteristics of large networks. We first men- [18] S. Suri. The Effects of Network Topology on Strategic tion several variants of community detection in networks Behavior. PhD thesis, Dept. of Computer and such as graph partitioning, finding the most dense subgraph Information Science, University of Pennsylvania, 2007.
in a given graph. Next we briefly mention various techniques [19] S. Wasserman and K. Faust. Social Network Analysis.
for community detection like spectral methods, multi-level Cambridge University Press, Cambridge, 1994.
methods, optimization methods, and methods based on so-

Source: http://wwwconference.org/proceedings/www2011/companion/p291.pdf