Most Influential Community Search over Large Social Networks
Most Influential Community Search over Large Social Networks
复制标题
DOI：
10.1109/icde.2017.136
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Jianxin Li;Xinjue Wang;Ke Deng;Xiaochun Yang;T. Sellis;J. Yu
中科院分区：
文献类型：
--
作者：
Jianxin Li;Xinjue Wang;Ke Deng;Xiaochun Yang;T. Sellis;J. Yu
在大型社交网络中检测社交社区为分析社交媒体用户的行为和活动提供了一种有效的方法。它引起了学术界和工业界的广泛关注。社交网络中社区的一个重要方面是外部影响，即将社区内部信息传播给外部用户的能力。检测高外部影响的社区在广泛的应用中具有特别的兴趣，例如，广告趋势分析，社会意见挖掘和新闻传播模式发现。然而，现有的检测技术在很大程度上忽略了社区的外部影响。为了填补这一空白，本文研究了最具影响力社区搜索问题，以揭示具有最高外部影响力的社区。本文首先提出了一种新的社区模型，即最大的k - clique社区，它具有社会性、凝聚力、连通性和最大性。然后，我们设计了一种新的基于树的索引结构，表示为C-Tree，以维护离线计算的r-cliques。为了有效地搜索最具影响力的社区，我们还开发了四种先进的基于索引的算法，将非索引解决方案的搜索性能提高了约200倍。我们的解决方案的效率和有效性已经通过六个真实数据集和一个小案例研究得到了广泛的验证。
Detecting social communities in large social networks provides an effective way to analyze the social media users' behaviors and activities. It has drawn extensive attention from both academia and industry. One essential aspect of communities in social networks is outer influence which is the capability to spread internal information of communities to external users. Detecting the communities of high outer influence has particular interest in a wide range of applications, e.g., Ads trending analytics, social opinion mining and news propagation pattern discovery. However, the existing detection techniques largely ignore the outer influence of the communities. To fill the gap, this work investigates the Most Influential Community Search problem to disclose the communities with the highest outer influences. We firstly propose a new community model, maximal kr-Clique community, which has desirable properties, i.e., society, cohesiveness, connectivity, and maximum. Then, we design a novel tree-based index structure, denoted as C-Tree, to maintain the offline computed r-cliques. To efficiently search the most influential communities, we also develop four advanced index-based algorithms which improve the search performance of non-indexed solution by about 200 times. The efficiency and effectiveness of our solution have been extensively verified using six real datasets and a small case study.