More Like this

1. Measuring the Impact of Influence on Individuals: Roadmap to Quantifying Attitude

   Fu, Xiaoyun ; Padmanabhan, Madhavan ; Kumar, Raj ; Basu, Samik ; Dorius, Shawn ; Pavan, A. ( October 2020 , {IEEE/ACM} International Conference on Advances in Social Networks Analysis and Mining, {ASONAM})

   Atzmuller, Martin ; Coscia, Michele ; Missaoui, Rokia (Ed.)

   Influence diffusion has been central to the study of the propagation of information in social networks, where influence is typically modeled as a binary property of entities: influenced or not influenced. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. We present an information diffusion model that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study the attitude maximization problem. We prove that the function for computing attitude is monotonic and sub-modular, and the attitude maximization problem is NP-Hard. We present a greedy algorithm for maximization with an approximation guarantee of $(1-1/e)$. Using the same model, we also introduce the notion of ``actionable'' attitude with the aim to study the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. We show that the function for computing actionable attitude, unlike that for computing attitude, is non-submodular but is approximately submodular. We present an approximation algorithm for maximizing actionable attitude in a network. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in the network such as spatial and value distribution of high attitude nodes. 

   more » « less
2. Triangular Stability Maximization by Influence Spread over Social Networks

   https://doi.org/10.14778/3611479.3611490  

   Hu, Zheng ; Zheng, Weiguo ; Lian, Xiang ( July 2023 , Proceedings of the VLDB Endowment)

   In many real-world applications such as social network analysis and online advertising/marketing, one of the most important and popular problems is called influence maximization (IM), which finds a set of k seed users that maximize the expected number of influenced user nodes. In practice, however, maximizing the number of influenced nodes may be far from satisfactory for real applications such as opinion promotion and collective buying. In this paper, we explore the importance of stability and triangles in social networks, and formulate a novel problem in the influence spread scenario, named triangular stability maximization , over social networks, and generalize it to a general triangle influence maximization problem, which is proved to be NP-hard. We develop an efficient reverse influence sampling (RIS) based framework for the triangle IM with theoretical guarantees. To enable unbiased estimators, it demands probabilistic sampling of triangles, that is, sampling triangles according to their probabilities. We propose an edge-based triple sampling approach, which is exactly equivalent to probabilistic sampling and avoids costly triangle enumeration and materialization. We also design several pruning and reduction techniques, as well as a cost-model-guided heuristic algorithm. Extensive experiments and a case study over real-world graphs confirm the effectiveness of our proposed algorithms and the superiority of triangular stability maximization and triangle influence maximization. 

   more » « less
3. Differentially Private Decomposable Submodular Maximization

   Chaturvedi, Anamay ; Nguyễn, Huy Lê ; Zakynthinou, Lydia ( May 2021 , Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance. 

   more » « less
4. Gaps in Information Access in Social Networks

   https://doi.org/10.1145/3308558.3313680  

   Fish, Benjamin ; Bashardoust, Ashkan ; Boyd, Danah ; Friedler, Sorelle ; Scheidegger, Carlos ; Venkatasubramanian, Suresh ( January 2019 , The Web Conference (WWW))

   The study of influence maximization in social networks has largely ignored disparate effects these algorithms might have on the individuals contained in the social network. Individuals may place a high value on receiving information, e.g. job openings or advertisements for loans. While well-connected individuals at the center of the network are likely to receive the information that is being distributed through the network, poorly connected individuals are systematically less likely to receive the information, producing a gap in access to the information between individuals. In this work, we study how best to spread information in a social network while minimizing this access gap. We propose to use the maximin social welfare function as an objective function, where we maximize the minimum probability of receiving the information under an intervention. We prove that in this setting this welfare function constrains the access gap whereas maximizing the expected number of nodes reached does not. We also investigate the difficulties of using the maximin, and present hardness results and analysis for standard greedy strategies. Finally, we investigate practical ways of optimizing for the maximin, and give empirical evidence that a simple greedy-based strategy works well in practice. 

   more » « less
5. A Community-Aware Framework for Social Influence Maximization

   Abhishek K. Umrawal, Christopher J. ( January 2023 , IEEE transactions on emerging topics in computational intelligence)

   We consider the problem of Influence Maximization (IM), the task of selecting k seed nodes in a social network such that the expected number of nodes influenced is maximized. We propose a community-aware divide-and-conquer framework that involves (i) learning the inherent community structure of the social network, (ii) generating candidate solutions by solving the influence maximization problem for each community, and (iii ) selecting the final set of seed nodes using a novel progressiv e budgeting scheme. Our experiments on real-world social networks show that the proposed framework outperforms the standard methods in terms of run-time and the heuristic methods in terms of influence. We also study the effect of the community structure on the performance of the proposed framework. Our experiments sho w that the community structures with higher modularity lead the proposed framework to perform better in terms of run-time an d influence. 

   more » « less