NS Seminar

Date and Location

Oct 30, 2018 - 3:30pm to 4:30pm
Bldg 434, Room 122


Signed Networks in Social Media (presented by Ishani Gupta, Computer Science)

Leskovec, J., Huttenlocher, D., & Kleinberg, J. (2010, April). Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems (pp. 1361-1370). ACM.

Relations between users on social media sites often reflect a mixture of positive (friendly) and negative (antagonistic) interactions. In contrast to the bulk of research on social networks that has focused almost exclusively on positive interpretations of links between people, we study how the interplay between positive and negative relationships affects the structure of on-line social networks. We connect our analyses to theories of signed networks from social psychology. We find that the classical theory of structural balance tends to capture certain common patterns of interaction, but that it is also at odds with some of the fundamental phenomena we observe — particularly related to the evolving, directed nature of these on-line networks. We then develop an alternate theory of status that better explains the observed edge signs and provides insights into the underlying social mechanisms. Our work provides one of the first large-scale evaluations of theories of signed networks using on-line datasets, as well as providing a perspective for reasoning about social media sites.


Strongly Stable Networks (presented Ryan Allen, Computer Science)

Jackson, M. O., & Van den Nouweland, A. (2005). Strongly stable networks. Games and Economic Behavior, 51(2), 420-444.

We analyze the formation of networks among individuals. In particular, we examine the existence of networks that are stable against changes in links by any coalition of individuals. We show that to investigate the existence of such strongly stable networks one can restrict focus on a component-wise egalitarian allocation of value. We show that when such strongly stable networks exist they coincide with the set of efficient networks (those maximizing the total productive value). We show that the existence of strongly stable networks is equivalent to core existence in a derived cooperative game and use that result to characterize the class of value functions for which there exist strongly stable networks via a “top convexity” condition on the value function on networks. We also consider a variation on strong stability where players can make side payments, and examine situations where value functions may be non-anonymous—depending on player labels.