March 2017 - Dm-meeting - mailman.cs.vt.edu

Monday March 27 @4pm, Sorour Amiri
by Sorour Ekhtiari Amiri 24 Mar '17

24 Mar '17

Hi everyone, Please join us for our next DM-Meeting. ****DM-Meeting Spring 2017**** WHO: Sorour E. Amiri WHEN: Monday, March 27, 2017, @ 4:00 pm WHERE: Torg 3160 A WHAT: I will talk about the following two papers: *(1) Do Cascades Recur?*. J. Cheng, L. Adamic, J. Kleinberg, J. Leskovec. ACM International Conference on World Wide Web (WWW), 2016. *Abstract*: Cascades of information-sharing are a primary mechanism by which content reaches its audience on social media, and an active line of research has studied how such cascades, which form as content is reshared from person to person, develop and subside. In this paper, we perform a large-scale analysis of cascades on Facebook over significantly longer time scales, and find that a more complex picture emerges, in which many large cascades recur, exhibiting multiple bursts of popularity with periods of quiescence in between. We characterize recurrence by measuring the time elapsed between bursts, their overlap and proximity in the social network, and the diversity in the demographics of individuals participating in each peak. We discover that content virality, as revealed by its initial popularity, is a main driver of recurrence, with the availability of multiple copies of that content helping to spark new bursts. Still, beyond a certain popularity of content, the rate of recurrence drops as cascades start exhausting the population of interested individuals. We reproduce these observed patterns in a simple model of content recurrence simulated on a real social network. Using only characteristics of a cascade’s initial burst, we demonstrate strong performance in predicting whether it will recur in the future. *(2) Inducing Domain-Specific Sentiment Lexicons from Unlabeled Corpora.* W. Hamilton, J. Leskovec, D. Jurafsky. Empirical Methods on Natural Language Processing (EMNLP), 2016. *Abstract*: A word’s sentiment depends on the domain in which it is used. Computational social science research thus requires sentiment lexicons that are specific to the domains being studied. We combine domain-specific word embeddings with a label propagation framework to induce accurate domain-specific sentiment lexicons using small sets of seed words. We show that our approach achieves state-of-the-art performance on inducing sentiment lexicons from domain-specific corpora and that our purely corpus-based approach outperforms methods that rely on hand-curated resources (e.g., WordNet). Using our framework, we induce and release historical sentiment lexicons for 150 years of English and community-specific sentiment lexicons for 250 online communities from the social media forum Reddit. The historical lexicons we induce show that more than 5% of sentiment-bearing (nonneutral) English words completely switched polarity during the last 150 years, and the community-specific lexicons highlight how sentiment varies drastically between different communities. Best regards, Sorour

1 0

Monday March 20 @4pm, Liangzhe Chen
by Sorour Ekhtiari Amiri 17 Mar '17

17 Mar '17

Hi everyone, Please join us for our next DM-Meeting. ****DM-Meeting Spring 2017**** WHO: Liangzhe Chen WHEN: Monday, March 20, 2017, @ 4:00 pm WHERE: Torg 3160 A WHAT: Liangzhe will talk about the following two papers: *(1) Exact Computation of Influence Spread by Binary Decision Diagrams, by Takanori Maehara et. al. WWW 2017* *Abstract*: Evaluating influence spread in social networks is a fundamental procedure to estimate the word-of-mouth effect in viral marketing. There are enormous studies about this topic; however, under the standard stochastic cascade models, the exact computation of influence spread is known to be #P-hard. Thus, the existing studies have used Monte-Carlo simulation-based approximations to avoid exact computation. We propose the first algorithm to compute influence spread exactly under the independent cascade model. The algorithm first constructs binary decision diagrams (BDDs) for all possible realizations of influence spread, then computes influence spread by dynamic programming on the constructed BDDs. To construct the BDDs efficiently, we designed a new frontier-based search-type procedure. The constructed BDDs can also be used to solve other influence-spread related problems, such as random sampling without rejection, conditional influence spread evaluation, dynamic probability update, and gradient computation for probability optimization problems. We conducted computational experiments to evaluate the proposed algorithm. The algorithm successfully computed influence spread on real-world networks with a hundred edges in a reasonable time, which is quite impossible by the naive algorithm. We also conducted an experiment to evaluate the accuracy of the Monte-Carlo simulation-based approximation by comparing exact influence spread obtained by the proposed algorithm. *(2) An Army of Me: Sockpuppets in Online Discussion Communities, by Srijan Kumar et. al. WWW 2017* *Abstract*: In online discussion communities, users can interact and share information and opinions on a wide variety of topics. However, some users may create multiple identities, or sockpuppets, and engage in undesired behavior by deceiving others or manipulating discussions. In this work, we study sockpuppetry across nine discussion communities, and show that sockpuppets differ from ordinary users in terms of their posting behavior, linguistic traits, as well as social network structure. Sockpuppets tend to start fewer discussions, write shorter posts, use more personal pronouns such as “I”, and have more clustered ego-networks. Further, pairs of sockpuppets controlled by the same individual are more likely to interact on the same discussion at the same time than pairs of ordinary users. Our analysis suggests a taxonomy of deceptive behavior in discussion communities. Pairs of sockpuppets can vary in their deceptiveness, i.e., whether they pretend to be different users, or their supportiveness, i.e., if they support arguments of other sockpuppets controlled by the same user. We apply these findings to a series of prediction tasks, notably, to identify whether a pair of accounts belongs to the same underlying user or not. Altogether, this work presents a data-driven view of deception in online discussion communities and paves the way towards the automatic detection of sockpuppets. Best regards, Sorour

1 0

Monday March 13 @4pm, Xinfeng Xu
by Sorour Ekhtiari Amiri 10 Mar '17

10 Mar '17

Hi everyone, Please join us for our next DM-Meeting. ****DM-Meeting Spring 2017**** WHO: Xinfeng Xu WHEN: Monday, March 13, 2017, @ 4:00 pm WHERE: Torg 3160 A WHAT: Xinfeng will talk about the following two papers: *1. Scaling up Link Prediction with Ensembles(WSDM 2016)* Abstract: A network with n nodes contains O(n^2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Furthermore, even though link prediction is closely related to missing value estimation problems, such as collaborative filtering, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity over very large networks. Due to this computational complexity, most known link prediction methods are designed for evaluating the link propensity over a specified subset of links, rather than for performing a global search over the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this paper, we propose an ensemble enabled approach to scaling up link prediction, which is able to decompose traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with the use of latent factor models, which can be effectively implemented over networks of modest size. Furthermore, the ensemble enabled approach has several advantages in terms of performance. We show the advantage of using ensemble-based latent factor models with experiments on very large networks. Experimental results demonstrate the effectiveness and scalability of our approach. *2. An efficient algorithm for link prediction in temporal uncertain social networks(Inf Sci 2016)* Abstract. Due to the inaccuracy, incompleteness and noise in data from real applications, uncertainty is a natural feature of real-world networks. In such networks, each edge is associated with a probability value indicating its existence in the network. Predicting links in uncertain networks is computationally more challenging and differs semantically from predicting connections in deterministic networks. This paper presents a method for link prediction in temporal uncertain networks. In our method, the predicting problem is formalized by designing a random walk in temporal uncertain networks. The algorithm first transforms the link prediction problem in uncertain networks to a random walk in a deterministic network. Then, the similarity scores between a node and its neighbors are computed within a sub-graph around this node to reduce the computational time. The proposed method integrates temporal and global topological information in temporal uncertain networks and can obtain more accurate results. Experimental results on real social networks show that our method can predict future links ef- ficiently in temporal uncertain social networks and achieves higher quality results than other similar methods. Best regards, Sorour

1 0

Meeting moved to March 7 @4 pm
by Sorour Ekhtiari Amiri 02 Mar '17

02 Mar '17

Hi all, Next DM-meeting will be on Tuesday, March 7 at 4:00 pm. It is only for the next week. Sorry for the inconvenience. Best regards, Sorour

1 0

DM-Meeting next week
by Sorour Ekhtiari Amiri 02 Mar '17

02 Mar '17

Hi everyone, Please join us for our next DM-Meeting. ****DM-Meeting Spring 2017**** WHO: Yao Zhang WHEN: Monday, March 6, 2017, @ 4:00 pm WHERE: Torg 3160 A WHAT: Yao will talk about the following two papers: *1) Task-Guided and Path-Augmented Heterogeneous Network Embedding for Author Identification. Ting Chen and Yizhou Sun. (WSDM 2017)* *Abstract: *In this paper, we study the problem of author identification under double-blind review setting, which is to identify potential authors given information of an anonymized paper. Different from existing approaches that rely heavily on feature engineering, we propose to use network embedding approach to address the problem, which can automatically represent nodes into lower dimensional feature vectors. However, there are two major limitations in recent studies on network embedding: (1) they are usually general-purpose embedding methods, which are independent of the specific tasks; and (2) most of these approaches can only deal with homogeneous networks, where the heterogeneity of the network is ignored. Hence, challenges faced here are two folds: (1) how to embed the network under the guidance of the author identification task, and (2) how to select the best type of information due to the heterogeneity of the network. To address the challenges, we propose a task-guided and path-augmented heterogeneous network embedding model. In our model, nodes are first embedded as vectors in latent feature space. Embeddings are then shared and jointly trained according to task-specific and network-general objectives. We extend the existing unsupervised network embedding to incorporate meta paths in heterogeneous networks, and select paths according to the specific task. The guidance from author identification task for network embedding is provided both explicitly in joint training and implicitly during meta path selection. Our experiments demonstrate that by using path-augmented network embedding with task guidance, our model can obtain significantly better accuracy at identifying the true authors comparing to existing methods. *2) Label Informed Attributed Network Embedding. Xiao Huang, Jundong Li, and Xia Hu. (WSDM 2017)* *Abstract*: Attributed network embedding aims to seek low-dimensional vector representations for nodes in a network, such that original network topological structure and node attribute proximity can be preserved in the vectors. These learned representations have been demonstrated to be helpful in many learning tasks such as network clustering and link prediction. While existing algorithms follow an unsupervised manner, nodes in many real-world attributed networks are often associated with abundant label information, which is potentially valuable in seeking more effective joint vector representations. In this paper, we investigate how labels can be modeled and incorporated to improve attributed network embedding. This is a challenging task since label information could be noisy and incomplete. In addition, labels are completely distinct with the geometrical structure and node attributes. The bewildering combination of heterogeneous information makes the joint vector representation learning more difficult. To address these issues, we propose a novel Label informed Attributed Network Embedding (LANE) framework. It can smoothly incorporate label information into the attributed network embedding while preserving their correlations. Experiments on real-world datasets demonstrate that the proposed framework achieves significantly better performance compared with the state-of-the-art embedding algorithms. Best regards, Sorour

1 0