基于影响路径的个性化影响最大化算法

个性化影响最大化问题是近年来社交网络影响最大化问题研究领域一个较新的分支,其现有解决方案普遍建立在网络边影响传播强度一致的假设下,该假设对于真实社交网络缺乏普遍适用性。为此基于独立级联模型,提出最大影响路径算法(MIPA)。该算法通过三个阶段来求解个性化影响最大化问题,首先将边影响强度作对数转换以获得最大影响路径,从而计算网络节点对目标节点的邻居节点的影响;然后利用多条经过目标节点邻居的最大影响路径联合计算目标节点受到的影响强度;最后选择Top-k节点作为种子节点,从而摆脱边影响强度的一致性约束,获取高质量的种子集。在不同的真实社交网络数据集上进行的对比实验验证了算法的有效性。     

社会网络中的影响力最大化问题

影响力最大化问题要求在网络中选取若干节点,使得以它们为初始节点进行信息传播时,在网络中产生的影响能够达到最大。影响力最大化问题是近十年来社会网络中的研究热点之一,其研究不仅具有理论意义,并且还具有应用前景。介绍了影响力最大化问题产生的背景,分析了问题的研究现状、研究用的几种主要传播模型以及解决问题的几种主要算法。最后,讨论了该研究面临的一些问题,对未来可能发展的研究方向进行了展望。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

Maximizing influence under influence loss constraint in social networks

Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, aims to select a small set of users to adopt a product, so that the word-of-mouth effect can subsequently trigger a large cascade of further adoption in social networks. The problem of influence maximization is to select a set of K nodes from a social network so that the spread of influence is maximized over the network. Previous research on mining top-K influential nodes assumes that all of the selected K nodes can propagate the influence as expected. However, some of the selected nodes may not function well in practice, which leads to influence loss of top-K nodes. In this paper, we study an alternative influence maximization problem which is naturally motivated by the reliability constraint of nodes in social networks. We aim to find top-K influential nodes given a threshold of influence loss due to the failure of a subset of R(<K) nodes. To solve the new type of influence maximization problem, we propose an approach based on constrained simulated annealing and further improve its performance through efficiently estimating the influence loss. We provide experimental results over multiple real-world social networks in support. This research will further support practical applications of social networks in various domains particularly where reliability would be a main concern in a system deployment.     

一种面向团体的影响最大化方法

影响最大化旨在从给定社会网络中寻找出一组影响力最大的子集.现有工作大都在假设实体点（个人或博客等）影响关系已知的情况下,关注于分析单个实体点的影响力.然而在一些实际场景中,人们往往更关注区域或人群等这类团体的组合影响力,如：户外广告,电视营销,疫情防控等.本文研究了影响力团体的选择问题：（1）基于团体的关联发现,我们建立了团体传播模型GIC（Group Independent Cascade）;（2）根据GIC模型,我们给出了贪心算法CGIM（Cascade Group influence maximization）搜索最具影响力的top-k团组合.在人工数据和真实数据上,实验验证了我们方法的效果和效率.     

基于社区划分的影响力最大化算法

影响力最大化问题是社会网络中的重要研究方向,其主要目的是获取社会网络中最有影响力的用户使通过这些用户获得影响传播范围的最大化。随着大数据时代的来临,传统的贪心算法因为复杂度高而不能有效解决大规模社会网络下影响力最大化的时间问题。提出一种基于社区划分的影响力最大化算法,利用影响概率将大规模社会网络分成较小的社区模块,并考虑社区边界节点之间的联系,从而最大程度缩小因社区划分造成的社区间的孤立。为进一步提高算法效率,在每个社区中以影响路径作为影响评估单元,同时对每个社区并行处理以便更高效地获取有影响力的节点。通过仿真实验验证了算法的可行性和高效性,其可以较好地适应大规模社会网络环境。     

Behavior‐Based Propagation of Trust in Social Networks with Restricted and Anonymous Participation

Increasing interactions and engagements in social networks through monetary and material incentives is not always feasible. Some social networks, specifically those that are built on the basis of fairness, cannot incentivize members using tangible things and thus require an intangible way to do so. In such networks, a personalized recommender could provide an incentive for members to interact with other members in the community. Behavior‐based trust models that generally compute social trust values using the interactions of a member with other members in the community have proven to be good for this. These models, however, largely ignore the interactions of those members with whom a member has interacted, referred to as “friendship effects.” Results from social studies and behavioral science show that friends have a significant influence on the behavior of the members in the community. Following the famous Spanish proverb on friendship “Tell Me Your Friends and I Will Tell You Who You Are,” we extend our behavior‐based trust model by incorporating the “friendship effect” with the aim of improving the accuracy of the recommender system. In this article, we describe a trust propagation model based on associations that combines the behavior of both individual members and their friends. The propagation of trust in our model depends on three key factors: the density of interactions, the degree of separation, and the decay of friendship effect. We evaluate our model using a real data set and make observations on what happens in a social network with and without trust propagation to understand the expected impact of trust propagation on the ranking of the members in the recommended list. We present the model and the results of its evaluation. This work is in the context of moderated networks for which participation is by invitation only and in which members are anonymous and do not know each other outside the community. Copyright © 2014 John Wiley & Sons, Ltd.     

基于有重叠社区划分的社会网络影响最大化方法研究

社会网络中影响最大化问题是指在特定传播模型下,对于给定的值,寻找具有最大影响范围的节点集,这是一个组合优化问题,Kempe等人已经证明该问题是NP-hard问题,其研究在理论和现实应用中都具有重大意义。文中提出一种新的影响最大化算法——有重叠社区划分的影响最大化算法(K-clique Heuristic算法),该算法的思路是在现实社会网络中跨越多个社交圈子的节点的传播领域越广,其交叉性更强、传播范围更广、影响力更大。所提算法与已有典型算法有相近的运行结果,且有更好的现实应用性和可解释性,为这项具有挑战性的研究提供了新的思路和方法。     

Identifying influential nodes in weighted complex networks using an improved WVoteRank approach

Influence maximization is an important research problem in the field of network science because of its business value. It requires the strategic selection of seed nodes called “influential nodes,” such that information originating from these nodes can reach numerous nodes in the network. Many real-world networks, such as transportation, communication, and social networks, are weighted networks. Influence maximization in a weighted network is more challenging compared to that in an unweighted network. Many methods, such as weighted degree rank, weighted h-index, weighted betweenness, and weighted VoteRank techniques, have been used to order the nodes based on their spreading capabilities in weighted networks. The VoteRank method is a popular method for finding influential nodes in an unweighted network using the idea of a voting scheme. Recently, the WVoteRank method was proposed to find the seed nodes; it extends the idea of the VoteRank method by considering the edge weights. This method considers only 1-hop neighbors to calculate the voting score of every node. In this study, we propose an improved WVoteRank method based on an extended neighborhood concept, which takes the 1-hop neighbors as well as 2-hop neighbors into account for the voting process to decide influential nodes in a weighted network. We also extend our proposed approach to unweighted networks. We compare the performance of the proposed improved WVoteRank method against the popular centrality measures, weighted degree, weighted closeness, weighted betweenness, weighted h-index, and weighted VoteRank on several real-life and synthetic datasets of diverse sizes and properties. We utilize the widely used stochastic susceptible–infected–recovered information diffusion model to calculate the infection scale, the final infected scale as a function of time, and the average distance between spreaders. The simulation results reveal that the proposed method, improved WVoteRank, considerably outperforms the other methods described above, including the recent WVoteRank.

     

Identification of top-k influential nodes based on discrete crow search algorithm optimization for influence maximization

Applied Intelligence - Influence maximization refers to selecting a small number of influential nodes in a given network to maximize the influence affected by the subset. In social network analysis...     

Using Estimated Personality of Social Network Members for Finding Influential Nodes in Viral Marketing

Sending promotional messages to a few numbers of users in a social network can propagate a product through word of mouth. However, choosing users that receive promotional messages, in order to maximize propagation, is a considerable issue. These recipients are named “influential nodes.” To recognize influential nodes, according to the literature, criteria such as the relationships of network members or information shared by each member on a social network have been used. One of the effective factors in diffusion of messages is the personality characteristics of members. As far as we know, although this issue is considerable, so far it has not been applied in the previous studies. In this article, using the graph structure of social networks, two personality characteristics, openness and extroversion, are estimated for network members. Next, these two estimated characteristics together with other characteristics of social networks, are considered as the criteria of choosing influential nodes. To implement this process, the real coded genetic algorithm is used. The proposed method has been evaluated on a dataset including 1000 members of Twitter. Our results indicate that using the proposed method, compared with simple heuristic methods, can improve performance up to 37%.     

面向微博的情感影响最大化模型

社交网络中影响最大化问题是寻找具有最大影响范围的节点。影响最大化的大部分求解算法仅仅依赖社交网络图。基于微博的转发关系树和微博内容的情感倾向性,以及用户的社交网络图,提出了一个能够刻画用户情感影响的情感影响最大化模型——情感影响分配模型(sentiment influence distribution,SID),证明了SID模型下的情感影响最大化问题是一个NP难问题,给出了一个具有精度保证的贪心算法。在真实的微博数据上的实验结果表明,SID模型能够有效地找出情感影响最大化的节点集,同时具有很高的扩展性。     

基于概率转移矩阵的社会网络影响最大化算法

现有近似求解影响最大化算法的时间复杂度较高,为此,提出一种扩展的线性阈值模型及其概率转移矩阵,给出该模型的传播过程及规则,设计基于概率转移矩阵的影响最大化算法,并利用贪心方法寻找到k个最具影响的节点。该算法通过矩阵乘积的方法得到,时刻节点之间的影响概率,无需在每个时刻计算所有非活跃节点的边际效益,从而在较短时间内提高运行时的效率,使得在规模较大的社会网络中被影响的节点最多且信息传播范围最广。仿真实验结果表明,在大规模社会网络中,该算法对社会网络节点的影响范围广且时间复杂度低。     

社会网络节点影响力分析研究

社会网络节点影响力研究是社会网络分析的关键问题之一.过去的十多年间,随着在线社会网络的快速发展,研究人员有机会在大量现实社会网络上对影响力进行分析和建模,并取得了丰硕的研究成果和广泛的应用价值.本文分析和总结了近年来社会网络影响力分析的主要成果.首先介绍了节点影响力的相关定义、作用范围以及表现形式;接着重点分类介绍节点影响力的度量方法,从网络拓扑、用户行为和内容分析3类方法总结了影响力的建模和度量方法;然后总结了影响力的传播和最大化模型相关成果;最后介绍了影响力的评价指标和应用.根据对现有方法的系统总结,对社会网络影响力的未来研究提出了一些值得关注的方向.     

Personalized Tag Recommendation Using Social Influence

Tag recommendation encourages users to add more tags in bridging the semantic gap between human concept and the features of media object,which provides a feasible solution for content-based multimedia information retrieval.In this paper,we study personalized tag recommendation in a popular online photo sharing site - Flickr.Social relationship information of users is collected to generate an online social network.From the perspective of network topology,we propose node topological potential to characterize user’s social influence.With this metric,we distinguish different social relations between users and find out those who really have influence on the target users.Tag recommendations are based on tagging history and the latent personalized preference learned from those who have most influence in user’s social network.We evaluate our method on large scale real-world data.The experimental results demonstrate that our method can outperform the non-personalized global co-occurrence method and other two state-of-the-art personalized approaches using social networks.We also analyze the further usage of our approach for the cold-start problem of tag recommendation.     

基于情感的社会网传播模型及影响最大化算法研究

针对社会网传播领域的影响最大化问题的研究，将节点本身具备的情感对事件传播的影响力进行了忽略，提出了基于情感的社会网传播模型（Emotion Independent Cascade model，E-IC），关于E-IC模型重点强调了情感影响的最大化基本问题（Influence Maximization Problem based on Emotion，IMPE），在传播整个进程中，融合了用户位置的计算值、后置情感的计算值以及交互概率值。论证并确认基于情感的社会网传播模型问题就是NP-hard问题，并给出近似算法EMS-Greedy。在训练集上调整模型参数，使得传播过程更符合传播规律，通过大规模真实数据集上的实验验证了E-IC模型的有效性。与其他模型相比，E-IC模型在传播范围上扩大了7%左右。     

Efficient algorithms for influence maximization in social networks

In recent years, due to the surge in popularity of social-networking web sites, considerable interest has arisen regarding influence maximization in social networks. Given a social network structure, the problem of influence maximization is to determine a minimum set of nodes that could maximize the spread of influences. With a large-scale social network, the efficiency and practicability of such algorithms are critical. Although many recent studies have focused on the problem of influence maximization, these works in general are time-consuming when a social network is large-scale. In this paper, we propose two novel algorithms, CDH-Kcut and Community and Degree Heuristic on Kcut/SHRINK, to solve the influence maximization problem based on a realistic model. The algorithms utilize the community structure, which significantly decreases the number of candidates of influential nodes, to avoid information overlap. The experimental results on both synthetic and real datasets indicate that our algorithms not only significantly outperform the state-of-the-art algorithms in efficiency but also possess graceful scalability.     

基于在线社会网络的用户影响力研究

对大规模的在线社会网络图结构进行了较为系统的分析,结果表明社会网络的入度、出度、发文数等基本符合幂律分布。社会网络的小世界属性也使得强连通关系呈现“纺锤体”形状。该文从用户的阅读概率角度引入用户的发文行为、浏览行为与标签社区小世界属性等对用户的社会影响力模型进行建模。实验结果显示PTIM模型融合了发文行为与小世界属性等特性,在最具影响力用户节点、用户粉丝数、认证用户数与人工标注的相对用户影响力大小等指标上均表现出稳定的性能。     

异质信息网络中基于邻接熵的影响力最大化

影响力最大化是研究如何在社会网络中寻找小部分最具影响力的节点作为信息扩散源,使信息在网络中传播范围最大的问题.已有相关研究大多只是针对同质信息网络,但现实中的社会网络是包含了多种对象类型和对象之间多种关系类型的异质网络,因此提出了基于元路径的邻接信息熵(MPAIE)模型,以及基于元图的邻接信息熵(MGAIE)模型来模拟异质信息网络中的社会影响.通过设置元路径或元图,该方法可以灵活地整合异质网络中的结构和语义信息,对节点的影响力做出度量,并在两个真实数据集上验证了MPAIE及MGAIE模型的有效性.