A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks
A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks
复制标题
DOI：
10.1109/tase.2010.2052042
复制
发表时间：
2011-01-01
影响因子：
5.6
通讯作者：
Narahari, Yadati
中科院分区：
文献类型：
--
作者：
Narayanam, Ramasuri;Narahari, Yadati
我们的研究关注的是当前一个重要的问题，即信息在社交网络中的传播。这个问题最近受到了互联网研究界的极大关注，受到许多潜在应用的推动，如病毒式营销和促销活动。在本文中，我们专注于目标集选择问题，这涉及到发现一个小的子集，有影响力的球员在一个给定的社会网络，执行一定的任务的信息扩散。目标集选择问题表现为两种形式：1）top-k节点问题和2）覆盖问题。在top-k节点问题中，我们需要找到一组k个关键节点，使网络中受影响的节点数量最大化。覆盖率问题涉及找到一组具有最小尺寸的k个关键节点，这些关键节点可以影响整个网络中给定百分比的节点。我们提出了一种新的方法来解决这些问题，使用Shapley值的概念，这是一个众所周知的解决方案的概念，在合作博弈论。我们的方法导致的算法，我们称之为沙普利值为基础的影响节点（SPIN）算法解决前k节点的问题和覆盖问题。我们比较了所提出的SPIN算法与文献中的知名算法的性能。通过对四个综合生成的随机图和六个真实数据集进行广泛的实验，（Celegans，Jazz，NIPS合著数据集，Netscience数据集，高能物理数据集和Political Books数据集），我们表明所提出的SPIN方法更强大，计算效率更高。社交网络由于其在改进网络搜索的性能、协同过滤系统中的推荐、使用病毒式营销技术在市场中传播技术众所周知，个人之间的人际关系（或纽带或联系）会导致社会系统的变化或改善，因为个人所做的决定会受到邻居行为的严重影响。社交网络中一个有趣而关键的问题是发现社交网络中最有影响力的节点，这些节点可以以强大而深入的方式影响社交网络中的其他节点。这个问题被称为目标集选择问题，有两个变体：1）前k个节点问题，我们需要识别一组k个有影响力的节点，使网络中受影响的节点数量最大化; 2）覆盖问题，涉及找到一组具有最小尺寸的有影响力的节点，这些节点可以影响整个网络中给定百分比的节点。在文献中有许多现有的算法来解决这些问题。在本文中，我们提出了一个新的算法，这是基于一个新的解释，在社会网络中的信息扩散作为一个合作游戏。使用这个类比，我们开发了一个算法的基础上的Shapley值的合作游戏。所提出的算法优于现有的算法在通用性或计算复杂度或两者兼而有之。我们的结果通过对合成生成的数据集和真实世界的数据集进行广泛的实验得到了验证。
Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient.Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.