论文类型：期刊论文
第一作者：Yuying Zhao
通讯作者：Pingpeng Yuan
合写作者：Yunfei Hu,Hai Jin
发表刊物：Data Science and Engineering
所属单位：计算机科学与技术学院
学科门类：工学
一级学科：计算机科学与技术
文献类型：J
期号：6
页面范围：339–357
发表时间：2021-05-29
摘要：Now, with the prevalence of social media, such as Facebook, Weibo, how to maximize influence of individuals, products, actions in new media is of practical significance. Generally, maximizing influence first needs to identify the most influential individuals since they can spread their influence to most of others in the social media. Many studies on influence maximization aimed to select a subset of nodes in static graphs once. Actually, real graphs are evolving. So, influential individuals are also changing. In these scenarios, people tend to select influential individuals multiple times instead of once. Namely, selections are raised sequentially, forming a sequence (query sequence). It raises several new challenges due to changing influential individuals. In this paper, we explore the problem of Influence Maximization over Streaming Graph (SGIM). Then, we design a compact solution for storing and indexing streaming graphs and influential nodes that eliminates the redundant computation. The solution includes Influence-Increment-Index along with two sketch-centralized indices called Influence-Index and Reverse-Influence-Index. Computing influence set of nodes will incur a large number of redundant computations. So, these indices are designed to keep track of the nodes’ influence in sketches. Finally, with the indexing scheme, we present the algorithm to answer SGIM queries. Extensive experiments on several real-world datasets demonstrate that our method is competitive in terms of both efficiency and effectiveness owing to the design of index.
发布期刊链接：https://link.springer.com/article/10.1007/s41019-021-00158-0