NS Seminar

Date and Location

Feb 22, 2017 - 2:00pm to 3:00pm
Bldg 434, room 122

Abstract

DeepWalk: Online Learning of Social Representations (presented by Furkan Kocayusufoglu, Computer Science)

Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

We present DeepWalk, a novel approach for learning latent representations of vertices in a network. These latent representations encode social relations in a continuous vector space, which is easily exploited by statistical models. Deep- Walk generalizes recent advancements in language modeling and unsupervised feature learning (or deep learning) from sequences of words to graphs. DeepWalk uses local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences. We demonstrate DeepWalk's latent representations on several multi-label network classication tasks for social networks such as Blog- Catalog, Flickr, and YouTube. Our results show that Deep- Walk outperforms challenging baselines which are allowed a global view of the network, especially in the presence of missing information. DeepWalk's representations can provide F1 scores up to 10% higher than competing methods when labeled data is sparse. In some experiments, Deep- Walk's representations are able to outperform all baseline methods while using 60% less training data. DeepWalk is also scalable. It is an online learning algorithm which builds useful incremental results, and is trivially parallelizable. These qualities make it suitable for a broad class of real world applications such as network classication, and anomaly detection.

 

Continuous-time model of structural balance (presented by Pedro Cisneros, Electrical and Computer Engineering)

S. A. Marvel, J. Kleinberg, and S. H. Stogatz, “Continuous-time model of structural balance,” Proceedings of the National Academy of Sciences, vol. 108, no. 5, pp. 1771–1776, Jan 2011.

It is not uncommon for certain social networks to divide into two opposing camps in response to stress. This happens, for example, in networks of political parties during winner-takes-all elections, in networks of companies competing to establish technical standards, and in networks of nations faced with mounting threats of war. A simple model for these two-sided separations is the dynamical system dX/dt = X2, where X is a matrix of the friendliness or unfriendliness between pairs of nodes in the network. Previous simulations suggested that only two types of behavior were possible for this system: Either all relationships become friendly or two hostile factions emerge. Here we prove that for generic initial conditions, these are indeed the only possible outcomes. Our analysis yields a closed-form expression for faction membership as a function of the initial conditions and implies that the initial amount of friendliness in large social networks (started from random initial conditions) determines whether they will end up in intractable conflict or global harmony.

 

Dynamical models explaining social balance and evolution of cooperation (presented by Pedro Cisneros, Electrical and Computer Engineering)

V. A. Traag, P. V. Dooren, and P. D. Leenheer, “Dynamical models explaining social balance and evolution of cooperation,” PLOS ONE, vol. 8, no. 4, pp. 1–7, 04 2013.

Social networks with positive and negative links often split into two antagonistic factions. Examples of such a split abound: revolutionaries versus an old regime, Republicans versus Democrats, Axis versus Allies during the second world war, or the Western versus the Eastern bloc during the Cold War. Although this structure, known as social balance, is well understood, it is not clear how such factions emerge. An earlier model could explain the formation of such factions if reputations were assumed to be symmetric. We show this is not the case for non-symmetric reputations, and propose an alternative model which (almost) always leads to social balance, thereby explaining the tendency of social networks to split into two factions. In addition, the alternative model may lead to cooperation when faced with defectors, contrary to the earlier model. The difference between the two models may be understood in terms of the underlying gossiping mechanism: whereas the earlier model assumed that an individual adjusts his opinion about somebody by gossiping about that person with everybody in the network, we assume instead that the individual gossips with that person about everybody. It turns out that the alternative model is able to lead to cooperative behaviour, unlike the previous model.