Detecting opinion leaders in online social networks using HybridRank algorithm

Abstract

Opinion leaders are those users who have great influence in social networks. It is significant to detect opinion leaders for the study on social networks and other applications. According to the key idea of the PageRank algorithm, a novel algorithm called HybridRank is proposed, taking into account topic-sensitive analysis and temporal characteristics. Our two major contributions are twofold: (1) topic-sensitive analysis is conducted to obtain the clusters in social networks; (2) temporal analysis is proposed to investigate the dynamics of the user’s influence over the time. We also provide impressive experimental analysis on a real dataset grabbed from Chinese Sina BBS, showing that the proposed HybridRank Algorithm outperforms various related approaches.

Keywords

Opinion leader PageRank algorithm topic-sensitive analysis temporal characteristics social networks

1 Introduction

Social networks, such as blogs, Facebook, Twitter and other social medium, have become increasingly popular for people to express their opinions in recent years. As more and more people prefer to publish their opinions on social networks, it is evident that some very active users who have great influence on other users, called opinion leader, play a crucial role in information propagation. For example, a company can sell their cool product through these influential persons, and thus a large population in the network would adopt the product through the word-of-mouth effect at a small cost. Consequently, the detection of these so-called opinion leader from a large amount of the users becomes a crucial issue. With respect to the spread of information, it is of great significance to detect these relatively more influential users.

Therefore, considerable attention has recently been devoted to detect opinion leaders as an important issue in social networks. At the current stage, numbers of methods for detecting opinion leaders focus on social relations based on Social Network Analysis (SNA). For instance, some researches detect the opinion leaders by using centrality-based metrics such as degree and betweenness [1]. Other studies put PageRank [2] and other modified PageRank algorithms (including LeaderRank [3] and PloarityRank [4]), which rank nodes according to the link structure features. Some other quantitative research is based on text analysis [5 –7], whose strongest advantage is to fully utilize the information of users, such as published comments and online time, in order to reconstruct the model of social networks and identify the opinion leaders more efficiently.

According to the previous presentation, we find that many methods rely on single method rather than by combining the methods above, which would not reflect accurately the importance of nodes for information dissemination. For instance, in a PageRank-based algorithm, its PageRank value is averagely distributed to outbound links; thus the algorithm ignores some information including topic information. The exiting of topic-sensitive phenomenon has attracted many scholars attention [4], i.e., a user follows his friend because he get interested in the topics his friend publishes, and his friend also follows back because they share similar topic interest. Moreover, PageRank algorithm has not concentrated on how temporal characteristics affect the published opinion of internet users. Considering users’ general browsing habits, a user likes the latest published opinions. And thus if a comment published earlier, it may has less influence. In summary, if we want to detect opinion leaders more accurately and analyze its characteristics as well as other useful metrics, it is not enough to put attention only on one measurement, but also needs to combine the methods above. This is exactly what we will do in the paper: detecting opinion leaders by taking into account the multiple measurements, which combines PageRank algorithm, topic-sensitive analysis and other useful characteristics such as temporal characteristics.

We address the context problem by proposing a novel approach to detect opinion leaders, called HybridRank Algorithm. The main framework of the proposed approach is illustrated as Fig. 1. In the pretreatment, some preprocessing is firstly conducted on the raw data, providing conditions for the subsequent process. Secondly, We conduct topic-sensitive analysis through the process called topic distillation, and give each node a particular value to express its topic characteristics. Then we use temporal characteristics to further examine the dynamics of influence, and a modified PageRank algorithm is conducted. Finally, focusing on different topics, we apply our HybridRank Algorithm, which combines PageRank algorithm, topic sensitive analysis and temporal characteristics, to rank users’ influence.

Fig.1

Framework of the proposed approach.

In summary, we address the efficiency problem of detection opinion leader from following two directions. In one direction, we propose a new method to further improve PageRank algorithm, and combine the original PageRank together with text analysis for more accurate results. Specially, by fully using of the topic-sensitive phenomenon, we propose our method to measure the topic-sensitive opinion leaders in social networks, which can further accurately detect opinion leaders. In other direction, we take into account temporal characteristics in the process of detecting opinion leaders, and investigate the dynamics of the user’s influence over the time.

The rest of the paper is organized as follows. Section 2 will overview previous works on detect opinion leaders. Section 3 will describe the basic ideas and methods of HybridRank algorithm. Section 4 will show our experiment results and analysis. We will conclude the research and give the future studies in Section 5.

2 Related work

Our work focus on the detection of opinion leaders in online social networks. And thus we give an overview of the related work in two aspects including Social Network Analysis and PageRank-based algorithms.

2.1 Social network analysis

Early Social Network Analysis mainly utilize link structures to detect nodes with high centrality including degree centrality value, closeness centrality, and betweenness centrality [1]. In the methods, the users are represented as nodes and the relations between users are represented as edges usually. In a simple social network, centrality theory prove to be theoretical and practical. These centrality measures capture the importance of nodes from different angles.

2.1.1 Degree centrality

The importance of a node is determined by the numbers of nodes link to it. The higher value of degree centrality would indicate a node has a larger number of connections with other nodes. Given a node k, the degree centrality can be defined as $DC (k) = \frac{d (k)}{N - 1}$ (1)

Here, N is the total number of nodes in the networks, and d (k) is the degree value of node k.

2.1.2 Closeness centrality

The global index measures the path it takes for a node to connect the rest nodes in a network. The shorter the average distance of a node to other nodes, the more direct and efficient is the node’s impact on the other nodes. Given a network having N nodes, the closeness centrality of node k is calculated as $CC (k) = \frac{N - 1}{\sum_{i = 1}^{N} d_{ki}} k \neq i$ (2)

Where d_ki is the length of the shortest path from node k to i in the network.

2.1.3 Betweenness centrality

The betweenness of nodes measures the number of shortest paths that will pass a node in the network. Specially, g_ij denotes the number of these shortest paths between nodes i and j, and g_ij (k) represents the number of these shortest paths that pass through node k. Therefore, the betweenness centrality of node k can be defined as $BC (k) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} \frac{g_{ij} (k)}{g_{ij}} i \neq j \neq k$ (3)

However, these centrality methods have a serious drawback, which is its efficiency. To get desired results reflecting the real networks properties, relying on one or more simple centrality methods would be impossible. What’s more, most recent social networks are large-scale and very dynamic, and also have complex link structures, which indicates the approach to the detection of opinion leaders needs to be very efficient and salable.

2.2 PageRank-based algorithms

PageRank algorithm is a sorting algorithm for link analysis and calculation of rank and importance on the Internet.The higher the level of a web page, the more prominent the importance, in the search engine rankings will appear on the front. It has two basic assumptions: (1) If a page is connected by other more pages, and perhaps it has greater importance; (2) If a page is connected by an important Web, it may be important too. Formally, the PageRank algorithm is described below. $PR (u) = (1 - d) + d \sum_{i = 1}^{n} \frac{PR (v_{i})}{C (v_{i})}$ (4) Where PR (u) and PR (v_i) represent the PageRank value of u and v_i, and v_i links u. C (v_i) is the number of the other page which v_i links to d is the damping factor, which is set to 0.85 as usual.

It is noted that, PageRank algorithm measures the influence only considering link structure of the network, rather than some other additional information, which does not accurately capture the notion of influence. For example, when using PageRank algorithm, a topic-drift phenomenon often happen. One of the main reasons of this phenomenon is that PageRank has nothing to do with the topic of queries. Therefore, a set of PageRank-based methods has been proposed to efficiently detect opinion leaders [3, 4]. The most similar work with ours is LeaderRank and TwitterRank. LeaderRank algorithm proposed by Xiao et al. [3] identifies opinion leaders in BBS, which contains two crucial steps, namely finding the clusters based on topic analysis and defining the authority value as the weight of the link between users. Weng et al. [4] present a TwitterRank algorithm to measure the topic-sensitive influence on Twitter by using Latent Dirichelet Allocation(LDA) [8, 9]. The experimental results show that both of their work(LeaderRank&&TwitterRank) outperforms the original PageRank and other related algorithms. Meanwhile, their work provide us new angles of addressing the shortcomings of PageRank algorithm by taking into account both link structure and topical information. However, LeaderRank and TwitterRank both neglect temporal characteristics in the networks. Therefore, we have deeper understanding about the influence and carries out extensive experiments to further examine temporal dynamics of influence, which is more in line with the real networks shown as the experimental results in Section 4.

3 Problem description

Considering a social network based on comment, users in the network prefer to browse their interested comments and reply them. Therefore, it is obvious that many users likely relate to each other with the same interesting topics. Based on above observation, a social network consists of three levels including topic layer, comment layer, and user layer illustrated as Fig. 2. There exists some relations mappings between different layers. For instance, users generate a comment which may be consist of several topics, and a topic may maps several comments.

Fig.2

Three layers of social networks.

Definition 1. (Comment network) Let C = {C₁, C₂, …, C_n} be a comment set, and C_i be an item of comment. Then G_CN (V, E) is a comment network (represented as a graph), which is composed of comments. Based on G_CN (V, E), it is probable to detect the most influential comment.

Definition 2. (User network) Let U = {U₁, U₂, …, U_m} be a user set, and then G_UN (V, E) is defined as a user network, which can express the relationship among users. Moreover, by using the mapping between comments and users, it can find out the most influential user, i,e, opinion leader.

Definition 3. (Opinion leader) As in Definition 2, based on some sorting method, each user in G_UN (V, E) has its own score, which can be assumed that Score_u1 > Score_u2 > … > Score_um. Therefore, the user with highest score are defined as opinion leader of users.

Our final goal is to efficiently detect opinion leader in G_UN (V, E), which may change over time. To achieve the goal, the paper takes the core ideas of original PageRank algorithm, and proposes a novel algorithm, i.e. HybridRank Algorithm, which is based on topic distillation and temporal analysis. We will do the following work which will be introduced in following section.

Modeling G_CN (V, E) and G_UN (V, E) based on connections between comments and users.

Topic distillation based on some cluster method.

Dynamic detection based on temporal analysis.

Detection of opinion leader by using exploring PageRank algorithm.

4 HybridRank algorithm

We will introduce our proposed HybridRank algorithm in detail, and analyze the affection factors including topic distillation and temporal characteristics in the section.

4.1 Raw data preprocess

After grabbing the related comments on a social network platform, we can construct the reply network among users directly, and identify the major information during a time period. Next, we will analyze the text information and apply ICTCLAS (Chinese Academy of Sciences Chinese Lexical Analysis System) [10] to split the title and body of comments into words. Formally, for two comments C_i and C_j in C = {C₁, C₂, …, C_n}, we first conduct some preprocessing by removing punctuation and eliminating stopwords from the comments. And then we split C_i and C_j into words respectively, and utilize a vector consisting of representative words to describe C_i and C_j. The vector C_k = {kw₁, kw₂, ⋯ , kw_n} denotes the comment C_k in the social networks, and kw_n means the key words in the comment. After that, we use TF-IDF [11, 12] to compute weighting by document frequency and inverse document frequency respectively, which has gained popularity in information retrieval assuming that the words are manually independent. Given a comment collection C, a word w, and an individual comment c ∈ C, we calculate $w_{c} = f_{w, c} * log (| C | / f_{w, C})$ (5)

Where f_w,c is the number of times w appears in comment c, |C| equals the size of the comment corpus, and f_w,C denotes the number of documents in which w appears in C.

After above process, we can describe every comment by Vector Space Model(VSM), which provide foundation for the subsequent process.

4.2 Cluster and topic distillation

Following work focus on clustering and classifying the comments according to the topics based on the proceeding definitions.

There exists many clustering algorithms including K-means [13], Hierarchical Clustering [14, 15] and other methods,which capture the clusters of documents in different perspectives. And it is difficult to define which is the “most suitable” algorithm for a problem regardless of the actual data distribution. However, in large-scale networks, most clustering algorithms are so computationally intensive that one may not get the results in a reasonable time except for K-means algorithm. K-means algorithm runs very fast, and doesn’t require calculating all of the distances between each nodes. Therefore, It can be applied to efficiently deal with very large data sets, where other methods may fail. In conclusion, we use K-means clustering algorithm as our topic distillation method rather than other methods.

Suppose that we have n comment vectors, and we know that they fall into K compact clusters, K < n. Moreover, we define the maximum number of iterations is L. The main steps of K-means is shown as following.

Step 1. Place K nodes into the space represented by the vectors c₁, c₂, …, c_K that are being clustered. These nodes is regarded as initial group centroids.

Step 2. Assign each vector to the group that has the closest centroid. The cluster label is determined by the function.

$\begin{matrix} label (i) = arg min_{j} {∥ C_{i} - C_{j} ∥}^{2}, \\ i = 1, \dots, n, j = 1, \dots, K \end{matrix}$ (6)

Step 3. When all nodes have been assigned, recalculate the positions of the K centroids.

$C_{j} = \frac{\sum_{s : label (s) = j} C_{s}}{N_{j}}, j = 1, 2, \dots, K$ (7)

Step 4. Repeat Steps 2 and 3 until the maximum iterations is reached. This produces a segmentation of the vectors into groups from which the metric to be minimized can be calculated.

The comments from social networks are divided into groups according to different topics after the process of K-means algorithm. In detail, the model has two parameters to be specified, i.e. the cluster number K, and the maximum number of iterations L. The Fig. 3 describes the detail of K-means where K is 3 and L means 3.

Fig.3

The representation of K-means algorithm.

Moreover, we suggest that each comment is accompanied by the representation of topics, and has at least one topic. As an example, when browsing comments we may incline to those comments on the interesting topics. Therefore, we can draw a conclusion that the impact of topic should be account. Therefore, we propose the following formula to further calculate the topic attribute for comment u:

$topic (u) = \frac{\sum_{u \in C_{i}} | C_{i} |}{| C |}$ (8)

Where C_i represents the set of cluster which comment u belongs(from K-means algorithm), and C is the total numbers of comments.

It can be seen that topic (u) express the ratio of the number of comments in the set which contains comment u to all the number of comments. The more the number of the comments in the set (which comment u belongs to) is, the larger the ratio is, which means it is more influential in the network.

4.3 Temporal analysis

Figure 4 demonstrates the trend of public opinion about the rainstorm disaster in Beijing, 2012. With the passage of time, the comments on the incident gradually reduced whether it was news or Weibo. Since July 22nd, the number of relevant Weibos significantly decreased. Similarly, the number of news reports greatly reduced since July 23rd. In the terms of information dissemination, the influence of the comments become more and more weak.

Fig.4

The trend of public opinion about the rainstorm disaster in Beijing.

Therefore, no matter news or Weibo is accompanied by the characteristics oftemporal, such as the time of the comment published. In detail, when reading comments, for instance, we may incline to overview those newly published comments rather than the earlier ones. It is interesting to find that there is a crucial relation between the publishing time of comment and its choice. Therefore, we believe that it is very reasonable to take the impact of time into account.

The paper solves the problem by defining a time reduction function f, which is accompanied by each comment. $f (t_{1}, t_{2}, D) = D^{| t_{2} - t_{1} |}$ (9)

Where f is a function relevant to damping coefficient D, time t₁ and t₂ is published time of the former and latter comment respectively. Therefore, if the latter comment is far from the former one, the probability of be visited is low. Additionally, the damping coefficient D is time- independent, and so we define f as the following formula. $f (t_{1}, t_{2}, D) = 1 + \frac{1}{2 * ln | t_{2} - t_{1} |}$ (10)

According to the formula above, the larger distance of |t₂ - t₁|, the smaller value of f (t₁, t₂, D) is. Moreover, with the increase of |t₂ - t₁| value, the value of f (t₁, t₂, D) tends to 1, which satisfies the convergence of the algorithm.

4.4 User influence rank

Opinion leaders play an important role in the procedure of information dissemination, who have a great impact on other users in social networks. Therefore, a novel rank method called HybridRank is proposed based on topic distillation and temporal analysis to detect opinion leaders in the paper.

Inspired by the original PageRank algorithm, HybridRank algorithm is presented by considering topic and temporal characteristics. Moreover, we set the topic factors of comments and temporal characteristics as weight of edges between users. For comment u in each topic, the ranking score can be calculated as following.

$\begin{matrix} PR (u) = ((1 - f (t_{1}, t_{2} D)) \\ + f (t_{1}, t_{2} D) * \sum_{i = 1}^{n} \frac{PR (v_{i})}{C (v_{i})}) * topic (u) \end{matrix}$ (11)

It can been seen that the above formula is similar to formula 4, i,e, f (t₁, t₂, D) displaces the originally damp quotient d in formula 4. In addition, we consider each comment is accompanied with a topic factor topic (u). If we conduct the above method, we will finally obtain the score of each comment in a time period. At last we select the user with the highest score as the opinion leader.

HybridRank algorithm is described in detail as Algorithm 1

Algorithm 1

HybridRank algorithm

Input: G (V, E);//V is the set of users, E is the edge;

Output: PR value; //Ranking score of each comment;

Description:

1. Cluster and topic distillation;//K-means method;

2. Foreach comment

3. {compute topic attribute topic (u) using formula 8;

4. compute temporal characteristics f (t₁, t₂, D) using

formula 10;

5. compute PR value using formula 11; }

7. Until convergence conditions are satisfied.

5 Experiments and analysis

In order to verify the correctness, extensive experimental analysis is carried out. The data for the experiment is crawled from Chinese Sina BBS, which exhibit many of the key features of social networks. Through tracking the comments all 2016 year round and splitting the period of time into four time segments, each time segment is analyzed to detect opinion leaders, and also the dynamic change of the opinion leaders is analyzed.

5.1 Experimental results

A dataset consisting of 347 users in Sina Sport forum is selected to validate effect of the proposed HybridRank algorithm in the paper. And the start time of the data is from January 1, 2016 to December, 2016. The dataset is grabbed including the authors and their replies from various forum “CBA”, “NBA”, “European Cup”, “Chinese football” and “Chinese volleyball”. And the basic information of the data set is illustrated as Table 1. It is obvious that the forum is a highly sparse network whose average clustering coefficient is only 0.28, with a small amount of nodes that are densely connected among them while being loosely connected to the rest of the graph.

Table 1
Basic statistics of Sina BBS data sets

Dataset statistics

Nodes 347

Edges 26112

Comment number 1731

Average clustering coefficient 0.28

Average Path length 4.63

Number of Strongly Connected 917

Components

Dataset statistics
Nodes	347
Edges	26112
Comment number	1731
Average clustering coefficient	0.28
Average Path length	4.63
Number of Strongly Connected	917
Components

The datasets is pretreated firstly, splitting by ICTCLAS which is an open-source software in Chinese. Secondly, the comments are clustered by their title and content and formatting different topics by using K-Means algorithm. The distribution of topics for the dataset is shown as Table 2. In order to provide a meaningful description, each topic are associated with 5 keywords that can mostly represent the content in the comments.

Table 2

The five topics extracted from the comments

Topics of Sina Sport forum	Keywords for each topic
CBA	Inside, Guo Ailun, Assists, Rebounds, Zhou Peng
NBA	America, Assists, Yi Jianlian, James, Warriors
European Cup	UEFA Champions League, Juventus, Italy, Rome, Milan
Chinese football	Hengda, Asia, Foreign aid, Patriotism, Qualify
Chinese volleyball	The Olympic Games, Women’s volleyball team, Block, China, Zhang Changning

The next is to analyze temporal characteristics for each comment. We solve the problem by calculating the value of time reduction function which is defined as formula 10. Each comment is accompanied by a value reflecting the temporal characteristics, which is convenient for our following dynamic analysis. Finally, we conduct our proposed HybridRank algorithm to detect opinion leader for every topic. Table 3 illustrates top-10 opinion leaders with the highest score according to formula 10.

Table 3

Top-10 opinion leaders for each topic within 2016 full year

Topic: CBA		Topic: NBA
User ID	OS(Leader value)	User ID	OS(Leader value)
119561022	1.96	324528563	1.49
235611348	1.44	415387461	1.11
490283521	1.36	534814673	1.10
190438754	1.25	347356109	1.09
389042859	1.24	224597164	1.08
298472957	1.13	571126346	1.07
789321901	1.12	612372906	1.06
473829432	1.12	316725441	1.06
862618493	1.12	518736992	1.06
198472837	1.10	433590266	1.05
Topic:Chinese football		Topic:European Cup
User ID	OS(Leader value)	User ID	OS(Leader value)
387356109	1.48	179023165	2.71
197943750	1.29	443671098	2.35
298472957	1.16	518034063	1.77
274561045	1.15	152293104	1.60
561283003	1.13	329849037	1.58
334178254	1.13	554913373	1.55
235611348	1.12	418034634	1.46
369813159	1.09	179322845	1.44
671598156	1.08	610966264	1.37
703349136	1.07	494783691	1.34
Topic:Chinese volleyball
User ID	OS(Leader value)
436915662	1.94
323458396	1.71
542833690	1.59
719026318	1.52
614427457	1.47
341099769	1.46
476619037	1.35
215633792	1.31
101443274	1.22
198204325	1.20

From the above table, we can observe that the opinion leaders is sensitive to the topics. Specially, if a user is an opinion leader in one topic, and perhaps it is just a follower in another topic. For example, the user with ID 119561022 is the opinion leader for the topic “CBA”, but ranks outside top-10 in other topics, which means that taking the topic into account is very necessary.

Additionally, we divide one year into four time segments, and each time segment is analyzed to identify opinion leaders, and also the dynamic change of the opinion leaders is analyzed which are shown as Fig. 5.

Fig.5

Different time segment ranking in 2016 full year.

From above figure, we find that opinion leaders are really changing over time. In other words, the rank of opinion leaders is also affected by the time. For example, in Fig. 5(a), the user with ID 190438754 had the highest score, meaning that it is the opinion leader in the time segment without question. In comparison with the rest figures, the user got fewer attention in the rest time of 2016 year. Therefore, it is very necessary to consider the time factor when detecting opinion leaders.

5.2 Comparison with other algorithm

To further find the effectiveness of HybridRank algorithm, we first compare the results of our proposed algorithm and PageRank algorithm directly as seen in Table 4.

Table 4
Comparison of the results of HybridRank algorithmand PageRank algorithm

Rank HybridRank Algorithm PageRank Algorithm

User ID OS (Leader value) User ID OS (Leader value)

1 235611348 0.88 179023165 2.71

2 389042859 0.81 436915662 2.43

3 323458396 0.80 443671098 2.35

4 436915662 0.75 119561022 1.82

5 298472957 0.73 518034063 1.79

6 190438754 0.68 323458396 1.70

7 369813159 0.67 329849037 1.61

8 197943750 0.66 542833690 1.59

9 547782953 0.64 152293104 1.58

10 387356109 0.60 554913373 1.55

Rank	HybridRank Algorithm	PageRank Algorithm
1	235611348	0.88	179023165	2.71
2	389042859	0.81	436915662	2.43
3	323458396	0.80	443671098	2.35
4	436915662	0.75	119561022	1.82
5	298472957	0.73	518034063	1.79
6	190438754	0.68	323458396	1.70
7	369813159	0.67	329849037	1.61
8	197943750	0.66	542833690	1.59
9	547782953	0.64	152293104	1.58
10	387356109	0.60	554913373	1.55

Table 4 shows top-10 opinion leaders using HybridRank and PageRank respectively. It is clear that the results are very different from each other, with only two repeat users with 323458396 and 436915662. Our proposed HybridRank Algorithm takes into account the multiple measurements, which combines PageRank algorithm, topic-sensitive analysis and temporal characteristics. Therefore, it can be used to enhance the importance of some users, and get reasonable results. For example, since the European Cup is held every four years, it has aroused great concern and more popular comments have been related in June and July, 2016. Therefore, the topic of European Cup has a larger wight. We can find some opinion leaders on the topic such as users “179023165”, “443671098”, “329849037” and “554913373” from Table 3. However, there was less and less attention to the European Cup as time goes on. And more and more people began to focus on important events such as NBA and CBA in November, and some new opinion leaders like users “235611348”, “190438754”, “389042859” and “298472957” were detected. It is worth noting that user “235611348” also pay particular attention to the topic of Chinese football with a relative higher score, and so it is the winner ranking by our proposed method.

Moreover we use Kendall’s coefficient τ [16] to show the degree of difference between them. The value range of τ is from – 1 to +1. The closer the value is to +1 or – 1, the stronger is the likely correlation. Table 5 demonstrates the correlation between HybridRank and degree centrality, closeness centrality, betweenness centrality, or PageRank measure. The lists of top 5 user ranking by HybridRank algorithm have a strong correlation, while a weak correlation with Betweenness centrality. The performance shows the τ value for the best-case scenario is 0.64.

Table 5

Kendall τ rank correlation coefficients

Correlation	Top 5	Top 10	Top 15	Top 20
HybridRank vs. PageRank	– 0.22	0.37	0.57	0.51
HybridRank vs. DC	– 0.31	0.41	0.63	0.52
HybridRank vs. CC	0.16	0.34	0.64	0.61
HybridRank vs. BC	0.04	– 0.10	0.29	0.48

6 Conclusion

We address the problem of detecting opinion leaders in social networks, and propose a novel algorithm called HybridRank based on original PageRank method. The algorithm takes into account the multiple measurements, which combines PageRank algorithm, topic-sensitive analysis and temporal characteristics. Focusing on Chinese Sina BBS, we study the dynamics of influence across topics and temporal. Experimental analysis demonstrates that our proposed HybridRank algorithm obtains better results comparing with other related algorithms. However, as an attempt to provide new lights on the research of opinion leaders, HybridRank algorithm still has space for improvement.

As part of future work, we plan to extend our framework in three directions. First, our current experiments only applied on special networks, and we plan to valid the proposed algorithm in a larger dataset. Second, so far we only considered some information including link, topic and temporal characteristics. In many applications, some other information i.e. sentiment characteristics is also very important. We are investigating how to incorporate these information into our method. Last but not least, an incremental approach for fast computation to detect opinion leaders is still a topic deserves further study.

Footnotes

Acknowledgments

This paper is supported by the Nature Science Foundation of China (No. 61502281,71403151).

References

Borgatti

S.P.

, Centrality and network flow G:/Tex/IOSPRESS/IFS/0-07/IF01.eps, SocialNetworks27 (1) (2005), 55–71.

Kandiah

and Shepelyansky

D.L.

, PageRank model of opinion formation on social networks[J], Physica A Statistical Mechanics & Its Applications391 (22) (2012), 5779–5793.

, Networking groups opinion leader identification algorithms based on sentiment analysis[J], Computer Science39 (2) (2012), 34–33.

Weng

, Lim

E.P.

, Jiang

, ., TwitterRank: Finding topic-sensitive influential twitterers [J], Wsdm (2010), 261–270.

Aisopos

, Papadakis

, Tserpes

, ., Content vs. context for sentiment analysis: A comparative analysisover microblogs[C]//, ACM Conference on Hypertext and Social Media ACM (2012), pp. 187–196.

Fiaidhi

, Mohammed

, ., Opinion mining over twitterspace: Classifying tweets programmatically using the R approach[C]//, Seventh International Conference on Digital Information Management IEEE (2012), pp. 313–319.

Zhang

, Ghosh

, Dekhil

, ., Combining Lexicon-based and Learning-based Methods for Twitter Sentiment Analysis[J], Hp Laboratories Technical Report, 2011.

Xue

, Journal of machine learning research[J], Journal of Machine Learning Research (2008).

Griffiths

T.L.

and Steyvers

, Finding scientific topics[J], Proceedings of the National Academy of Sciences of the United States of America101(Suppl 1)(1) (2004), 5228.

10.

and Zhang

, Research on enhancing the effectiveness of the Chinese text automatic categorization based on ICTCLAS segmentation method[J], (2013), pp. 267–270.

11.

Salton

and Buckley

, Term-weighing approache sin automatic text retrieval, Information Processing & Management24 (5) (1988), 513–523.

12.

Berger

, Caruana

, Cohn

, ., Bridging the lexical chasm: Statistical approaches to answer-finding[C]//, International ACM SIGIR Conference on Research and Development in Information Retrieval ACM (2000), pp. 192–199.

13.

Macqueen

, Some Methods for Classification and Analysis of MultiVariate Observations[C]//, Proc of Berkeley Symposium on Mathematical Statistics and Probability (1967), pp. 281–297.

14.

Sibson

, Slink: An optimally efficient algorithm for the single-link cluster method[J], Computer Journal16 (1) (1973).

15.

Defays

, An efficient algorithm for a complete link method[J], Computer Journal20(4) (1977), 364–366.

16.

Kendall

M.G.

, A new measure of rank correlation[J], Biometrika30(1/2) (1938), 81–93.