You are here

Session Details

Social Networks 3

Thursday, 13 December
10:00 – 12:00
Room: Salle des nations I & II
Session Chair: Feida ZHU

10:00 Topic-aware Social Influence Propagation Models short_paper) echo(" (Short)");?>
Nicola Barbieri, Francesco Bonchi, and Giuseppe Manco

We study social influence from a topic modeling perspective. We introduce novel topic-aware influence-driven propagation models that experimentally result to be more accurate in describing real-world cascades than the standard propagation models studied in the literature. In particular, we first propose simple topic-aware extensions of the well-known Independent Cascade and Linear Threshold models. Next, we propose a different approach explicitly modeling authoritativeness, influence and relevance under a topic-aware perspective. We devise methods to learn the parameters of the models from a dataset of past propagations. Our experimentation confirms the high accuracy of the proposed models and learning schemes.

10:20 Profit Maximization over Social Networks short_paper) echo(" (Short)");?>
Wei Lu and Laks V. S. Lakshmanan

Influence maximization is the problem of finding a set of influential users in a social network such that the expected spread of influence under a certain propagation model is maximized. Much of the previous work has neglected the important distinction between social influence and actual product adoption. However, as recognized in the management science literature, an individual who gets influenced by social acquaintances may not necessarily adopt a product (or technology), due, e.g., to monetary concerns. In this work, we distinguish between influence and adoption by explicitly modeling the states of being influenced and of adopting a product. We extend the classical Linear Threshold (LT) model to incorporate prices and valuations, and factor them into users' decision-making process of adopting a product. We show that the expected profit function under our proposed model maintains submodularity under certain conditions, but no longer exhibits monotonicity, unlike the expected influence spread function. To maximize the expected profit under our extended LT model, we employ an unbudgeted greedy framework to propose three profit maximization algorithms. The results of our detailed experimental study on three real-world datasets demonstrate that of the three algorithms, PAGE, which assigns prices dynamically based on the profit potential of each candidate seed, has the best performance both in the expected profit achieved and in running time.

10:40 Diffusion of Information in Social Networks: Is It All Local? short_paper) echo(" (Short)");?>
Ceren Budak, Divyakant Agrawal, and Amr El Abbadi

Recent studies on the diffusion of information in social networks have largely focused on models based on the influence of local friends. In this paper, we challenge the generalizability of this approach and revive theories introduced by social scientists in the context of diffusion of innovations to model user behavior. To this end, we study various diffusion models in two different online social networks, Digg and Twitter. We first evaluate the applicability of two representative local influence models and show that the behavior of most social networks users are not captured by these local models. Next, driven by theories introduced in the diffusion of innovations research, we introduce a novel diffusion model called Gaussian Logit Curve Model (GLCM) that models user behavior with respect to the behavior of the general population. Our analysis shows that GLCM captures user behavior significantly better than local models, especially in the context of Digg. Aiming to capture both the local and global signals, we introduce various hybrid models and evaluate them through statistical methods. Our methodology models each user separately, automatically determining which users are driven by their local relations and which users are better defined through adopter categories, therefore capturing the complexity of human behavior.

11:00 Clash of the Contagions: Cooperation and Competition in Information Diffusion short_paper) echo(" (Short)");?>
Seth A. Myers and Jure Leskovec

In networks, contagions such as information, purchasing behaviors, and diseases, spread and diffuse from node to node over the edges of the network. Moreover, in real-world scenarios multiple contagions spread through the network simultaneously. These contagions not only propagate at the same time but they also interact and compete with each other as they spread over the network. While traditional empirical studies and models of diffusion consider individual contagions as independent and thus spreading in isolation, we study how different contagions interact with each other as they spread through the network. We develop a statistical model that allows for competition as well as cooperation of different contagions in information diffusion. Competing contagions decrease each other's probability of spreading, while cooperating contagions help each other in being adopted throughout the network. We evaluate our model on 18,000 contagions simultaneously spreading through the Twitter network. Our model learns how different contagions interact with each other and then uses these interactions to more accurately predict the diffusion of a contagion through the network. Moreover, the model also provides a compelling hypothesis for the principles that govern content interaction in information diffusion. Most importantly, we find very strong effects of interactions between contagions. Interactions cause a relative change in the spreading probability of a contagion by em 71% on the average.

11:20 Link Prediction and Recommendation across Heterogenous Social Networks short_paper) echo(" (Short)");?>
Yuxiao Dong, Jie Tang, Sen Wu, Jilei Tian, Nitesh V. Chawla, Jinghai Rao, and Huanhuan Cao

Link prediction and recommendation is a fundamental problem in social network analysis. The key challenge of link prediction comes from the sparsity of networks due to the strong disproportion of links that they have potential to form to links that do form. Most previous work tries to solve the problem in single network, few research focus on capturing the general principles of link formation across heterogeneous networks. In this work, we give a formal definition of link recommendation across heterogeneous networks. Then we propose a ranking factor graph model (RFG) for predicting links in social networks, which effectively improves the predictive performance. Motivated by the intuition that people make friends in different networks with similar principles, we find several social patterns that are general across heterogeneous networks. With the general social patterns, we develop a transfer-based RFG model that combines them with network structure information. This model provides us insight into fundamental principles that drive the link formation and network evolution. Finally, we verify the predictive performance of the presented transfer model on 12 pairs of transfer cases. Our experimental results demonstrate that the transfer of general social patterns indeed help the prediction of links.

11:40 Predicting Links in Multi-Relational and Heterogeneous Networks short_paper) echo(" (Short)");?>
Yang Yang, Nitesh V. Chawla, Yizhou Sun, and Jiawei Han

Link prediction is an important task in network analysis, benefiting researchers and organizations in a variety of fields. Many networks in the real world, for example social networks, are heterogeneous, having multiple types of links and complex dependency structures. Link prediction in such networks must model the influence propagating between heterogeneous relationships to achieve better link prediction performance than in homogeneous networks. In this paper, we introduce Multi-Relational Influence Propagation (MRIP), a novel probabilistic method for heterogeneous networks. We demonstrate that MRIP is useful for predicting links in sparse networks, which present a significant challenge due to the severe disproportion of the number of potential links to the number of real formed links. We also explore some factors that can inform the task of classification yet remain unexplored, such as temporal information. In this paper we make use of the temporal-related features by carefully investigating the issues of feasibility and generality. In accordance with our work in unsupervised learning, we further design an appropriate supervised approach in heterogeneous networks. Our experiments on co-authorship prediction demonstrate the effectiveness of our approach.