Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEvolving Influence Maximization in Evolving Networks
92
0
0.0
(
0
)
Added by
Xudong Wu
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Influence Maximization (IM) aims to maximize the number of people that become aware of a product by finding the `best set of `seed users to initiate the product advertisement. Unlike prior arts on static social networks containing fixed number of users, we undertake the first study of IM in more realistic evolving networks with temporally growing topology. The task of evolving IM ({bfseries EIM}), however, is far more challenging over static cases in the sense that seed selection should consider its impact on future users and the probabilities that users influence one another also evolve over time. We address the challenges through $mathbb{EIM}$, a newly proposed bandit-based framework that alternates between seed nodes selection and knowledge (i.e., nodes growing speed and evolving influences) learning during network evolution. Remarkably, $mathbb{EIM}$ involves three novel components to handle the uncertainties brought by evolution:
rate research
Read More
Social networks have been popular platforms for information propagation. An important use case is viral marketing: given a promotion budget, an advertiser can choose some influential users as the seed set and provide them free or discounted sample products; in this way, the advertiser hopes to increase the popularity of the product in the users friend circles by the world-of-mouth effect, and thus maximizes the number of users that information of the production can reach. There has been a body of literature studying the influence maximization problem. Nevertheless, the existing studies mostly investigate the problem on a one-off basis, assuming fixed known influence probabilities among users, or the knowledge of the exact social network topology. In practice, the social network topology and the influence probabilities are typically unknown to the advertiser, which can be varying over time, i.e., in cases of newly established, strengthened or weakened social ties. In this paper, we focus on a dynamic non-stationary social network and design a randomized algorithm, RSB, based on multi-armed bandit optimization, to maximize influence propagation over time. The algorithm produces a sequence of online decisions and calibrates its explore-exploit strategy utilizing outcomes of previous decisions. It is rigorously proven to achieve an upper-bounded regret in reward and applicable to large-scale social networks. Practical effectiveness of the algorithm is evaluated using both synthetic and real-world datasets, which demonstrates that our algorithm outperforms previous stationary methods under non-stationary conditions.
Given a directed graph (representing a social network), the influence maximization problem is to find k nodes which, when influenced (or activated), would maximize the number of remaining nodes that get activated. In this paper, we consider a more general version of the problem that includes an additional set of nodes, termed as physical nodes, such that a node in the social network is covered by one or more physical nodes. A physical node exists in one of two states at any time, opened or closed, and there is a constraint on the maximum number of physical nodes that can be opened. In this setting, an inactive node in the social network becomes active if it has enough active neighbors in the social network and if it is covered by at least one of the opened physical nodes. This problem arises in disaster recovery, where a displaced social group decides to return after a disaster only after enough groups in its social network return and some infrastructure components in its neighborhood are repaired. The general problem is NP-hard to approximate within any constant factor and thus we characterize optimal and approximation algorithms for special instances of the problem.
The majority of real-world networks are dynamic and extremely large (e.g., Internet Traffic, Twitter, Facebook, ...). To understand the structural behavior of nodes in these large dynamic networks, it may be necessary to model the dynamics of behavioral roles representing the main connectivity patterns over time. In this paper, we propose a dynamic behavioral mixed-membership model (DBMM) that captures the roles of nodes in the graph and how they evolve over time. Unlike other node-centric models, our model is scalable for analyzing large dynamic networks. In addition, DBMM is flexible, parameter-free, has no functional form or parameterization, and is interpretable (identifies explainable patterns). The performance results indicate our approach can be applied to very large networks while the experimental results show that our model uncovers interesting patterns underlying the dynamics of these networks.
Temporal communities result from a consistent partitioning of nodes across multiple snapshots of an evolving complex network that can help uncover how dense clusters in a network emerge, combine, split and decay with time. Current methods for finding communities in a single snapshot are not straightforwardly generalizable to finding temporal communities since the quality functions used for finding static communities have highly degenerate landscapes, and the eventual partition chosen among the many partitions of similar quality is highly sensitive to small changes in the network. To reliably detect temporal communities we need not only to find a good community partition in a given snapshot but also ensure that it bears some similarity to the partition(s) found in immediately preceding snapshots. We present a new measure of partition distance called estrangement motivated by the inertia of inter-node relationships which, when incorporated into the measurement of partition quality, facilitates the detection of meaningful temporal communities. Specifically, we propose the estrangement confinement method, which postulates that neighboring nodes in a community prefer to continue to share community affiliation as the network evolves. Constraining estrangement enables us to find meaningful temporal communities at various degrees of temporal smoothness in diverse real-world datasets. Specifically, we study the evolution of voting behavior of senators in the United States Congress, the evolution of proximity in human mobility datasets, and the detection of evolving communities in synthetic networks that are otherwise hard to find. Estrangement confinement thus provides a principled approach to uncovering temporal communities in evolving networks.
Influence maximization (IM) aims at maximizing the spread of influence by offering discounts to influential users (called seeding). In many applications, due to users privacy concern, overwhelming network scale etc., it is hard to target any user in the network as one wishes. Instead, only a small subset of users is initially accessible. Such access limitation would significantly impair the influence spread, since IM often relies on seeding high degree users, which are particularly rare in such a small subset due to the power-law structure of social networks. In this paper, we attempt to solve the limited IM in real-world scenarios by the adaptive approach with seeding and diffusion uncertainty considered. Specifically, we consider fine-grained discounts and assume users accept the discount probabilistically. The diffusion process is depicted by the independent cascade model. To overcome the access limitation, we prove the set-wise friendship paradox (FP) phenomenon that neighbors have higher degree in expectation, and propose a two-stage seeding model with the FP embedded, where neighbors are seeded. On this basis, for comparison we formulate the non-adaptive case and adaptive case, both proven to be NP-hard. In the non-adaptive case, discounts are allocated to users all at once. We show the monotonicity of influence spread w.r.t. discount allocation and design a two-stage coordinate descent framework to decide the discount allocation. In the adaptive case, users are sequentially seeded based on observations of existing seeding and diffusion results. We prove the adaptive submodularity and submodularity of the influence spread function in two stages. Then, a series of adaptive greedy algorithms are proposed with constant approximation ratio.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
