Ankan Mullick, Sombit Bose, Rounak Saha, Ayan Kumar Bhowmick, Aditya Vempaty, Prasenjit Dey, Ravi Kokku, Pawan Goyal, Niloy Ganguly. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

Twitter is currently a popular microblogging platform for spread of information by users in the form of tweet messages. Such tweets are shared with followers of the seed user who may reshare it with their own set of followers. Long chain of such retweets form cascades. For effective diffusion of information through such Twitter cascades, we identify two different objectives based on using temporal sequence of retweets. Firstly, we aim to infer the structure of influence trees of Twitter cascades, denoting the who-influenced-whom relationship among retweeting users in the cascade, that can play a significant role in identifying critical paths in the network for information dissemination. The constructed trees closely resemble ground truth influence trees of empirical cascades with high retweet count. Secondly, we propose a fast and efficient algorithm for detection of influential users by identifying anchor nodes from temporal retweet sequence. Identification of such a diverse set of influential users enable a faster diffusion of tweets to a large and diverse population, when targeted as seeds thereby maximizing the influence spread, facilitating several applications including viral marketing, disease control and news dissemination.

Network embedding, that aims to learn low-dimensional vector representation of nodes such that the network structure is preserved, has gained significant research attention in recent years. However, most state-of-the-art network embedding methods are computationally expensive and hence unsuitable for representing nodes in billion-scale networks. In this paper, we present LouvainNE, a hierarchical clustering approach to network embedding. Precisely, we employ Louvain, an extremely fast and accurate community detection method, to build a hierarchy of successively smaller subgraphs. We obtain representations of individual nodes in the original graph at different levels of the hierarchy, then we aggregate these representations to learn the final embedding vectors. Our theoretical analysis shows that our proposed algorithm has quasi-linear run-time and memory complexity. Our extensive experimental evaluation, carried out on multiple real-world networks of different scales, demonstrates both (i) the scalability of our proposed approach that can handle graphs containing tens of billions of edges, as well as (ii) its effectiveness in performing downstream network mining tasks such as network reconstruction and node classification.

Identification of influential users in online social networks allows to facilitate efficient information diffusion to a large part of the network and thus benefiting diverse applications including viral marketing, disease control, and news dissemination. Existing methods have mainly relied on the network structure only for the detection of influential users. In this paper, we enrich this approach by proposing a fast, efficient, and unsupervised algorithm SmartInf to detect a set of influential users by identifying anchor nodes from a temporal sequence of retweets in Twitter cascades. Such anchor nodes provide important signatures of tweet diffusion across multiple diffusion localities and, hence, act as precursors for detection of influential nodes.1The set of influential nodes identified by SmartInf has the capacity to expose the tweet to a large and diverse population, when targeted as seeds thereby maximizing the influence spread. Experimental evaluation on empirical datasets from Twitter shows the superiority of SmartInf over state-of-the-art baselines in terms of infecting larger population; further, our evaluation shows that SmartInf is scalable to large-scale networks and is robust to missing data. Finally, we investigate the key factors behind the improved performance of SmartInf by testing our algorithm on a synthetic network using synthetic cascades simulated on this network. Our results reveal the effectiveness of SmartInf in identifying a diverse set of influential users that facilitate faster diffusion of tweets to a larger population.1We use the terms “influential nodes” and “influential users” interchangeably.

Twitter is currently a popular microblogging platform for the dissemination of information by users in the form of messages such as tweets. Such tweets are shared with followers of the seed user who in turn may reshare it with their own set of followers. Long chain of such retweets form cascades. In this paper, we aim to estimate the influence tree of cascades denoting the who-influenced-whom relationship among retweeting users by leveraging on temporal pattern of its retweets. We use a principled methodology to construct the ground truth influence trees of cascades using standard diffusion models. We define diverse structural metrics to quantify the structural characteristics of different influence trees. Based on empirical observations from ground truth, we develop CasCon, an unsupervised model that leverages on temporal pattern of retweets obtained from time series of cascades and underlying follower network of Twitter to construct influence trees. Further, we provide an analytical formulation of CasCon by deriving the degree distribution of these predicted influence trees and use it to approximate the structural metrics. Our evaluation shows that CasCon exhibits superior performance compared to state-of-theart baseline algorithms in selecting influencers of high quality based on standard influence measures in Twitter as well as in correctly (re)constructing the ground truth influence trees with high accuracy. Finally, we validate the analytical formulation of CasCon on the influence tree structures of both synthetic and real cascades; experimental results demonstrate its effectiveness in closely resembling ground truth influence trees for empirical cascades with high retweet count.

Twitter has recently become one of the most popular online social networking websites where users can share news and ideas through messages in the form of tweets. As a tweet gets retweeted from user to user, large cascades of information diffusion are formed over the Twitter follower network. Existing works on cascades have mainly focused on predicting their popularity in terms of size. In this paper, we leverage on the temporal pattern of retweets to model the diffusion dynamics of a cascade. Notably, retweet cascades provide two complementary information: (a) inter-retweet time intervals of retweets, and (b) diffusion of cascade over the underlying follower network. Using datasets from Twitter, we identify two types of cascades based on presence or absence of early peaks in their sequence of inter-retweet intervals. We identify multiple diffusion localities associated with a cascade as it propagates over the network. Our studies reveal the transition of a cascade to a new locality facilitated by pivotal users that are highly cascade dependent following saturation of current locality. We propose an analytical model to show co-occurrence of first peaks and cascade migration to a new locality as well as predict locality saturation from inter-retweet intervals. Finally, we validate these claims from empirical data showing co-occurrence of first peaks and migration with good accuracy; we obtain even better accuracy for successfully classifying saturated and non-saturated diffusion localities from inter-retweet intervals.

The penetration of smartphones and advancement of the location-based services have jointly contributed to the popularity of location-based social networking platforms such as Foursquare and Yelp. Business owners are important stakeholders of such location-based social network (LBSN) platforms, for whom setting up new businesses at the right location has immense importance in making a business popular. Given a wide variety of businesses, a single metric may not correctly capture the business popularity, rather, popularity measure should be specific to geographical regions, business category etc. In this paper, we systematically define popularity metrics and use them to label diverse businesses available in Yelp dataset. Notably, information diffusion plays a major role in popularizing businesses, word of mouth communication across customers facilitates information spread. This paper concentrates on two key modalities that exhibit a strong signature of business popularity: social connections across customers, showing high correlation with corresponding business popularity, and geographical proximity, which reveals two types of customers, namely, local visitor and foreign visitor observed through a comprehensive study on Yelp dataset. Depending on the business type and category, either local or foreign visitors play important role in making a business popular. Finally, we leverage on these signatures to predict business popularity and develop a recommendation model suggesting top regions to business owners for starting popular businesses. We show that both the models outperform the state-of-the-art baseline algorithms.