关键词: 在线社交网络, 影响力排序算法, 影响力评价, PageRank改进

Abstract:

In large Online Social Networks (OSNs), sorting nodes according to their influence is an important research issue. The most influential (set of) nodes can be found by sorting nodes, which is essential to the control of information dissemination, public opinion control and analyses, and onpurpose advertising. Existing influence sorting algorithms either need global topology information of the network to calculate the influence of individual nodes (e.g., the betweennessbased algorithms), which are usually time consuming and thus are not applicable to large scale networks, or use the traditional sorting algorithms designed for web page ranking (e.g., PageRank), which cannot well handle the properties of OSNs like the existence of end nodes and different relationship between different nodes. The traditional PageRank algorithm is enhanced from two aspects to make it applicable to node sorting in large scale OSNs. Firstly, different residual weights are assigned to nodes according to the weights of links in the weight collection phase of PageRank, which effectively mitigates the negative influence of end nodes on the sorting accuracy. Secondly, in the voting process, the diversity among different nodes is considered and a neighborhood based algorithm is proposed to assign weights to different nodes, which effectively improve the sorting accuracy. The performance of the proposed algorithm is evaluated on a sample network constructed with 15,000 real users sampled from Sina Weibo. It is shown that the enhanced algorithm can find more than 40% of the 1000 most influential nodes in the sample network, while the traditional PageRank algorithm counterpart can find only 11%. Meanwhile, compared with the betweennessbased algorithms, the proposed algorithm achieves similar or even better sorting accuracy with much less time cost.

Key words: online social networks;influence node sorting;influence evaluation;PageRank improvement