# Analysis of the Dynamic Influence of Social Network Nodes

Authors: Hong-Jian Yin; Hai Yu; Yu-Li Zhao; Zhi-Liang Zhu; Wei Zhang
Journal: Scientific Programming
 (2017)

---

## Abstract

In recent years, with the development of the social network theories, how to find or mining the most significant node in social network for understanding or controlling the information dissemination has become a hot topic and a series of effective algorithms have been presented. In this paper, a new scheme to measure the dynamic influence of the nodes in a social network is proposed, in which the sum of trust values of the propagation nodes is used. Simulations have been carried out and the results show that our scheme is stable and accurate.


---

## Body

## 1. Introduction

In the past decades, the revolutionary developments of communication tools have made significant changes to peoples social relationships. In the 1960s, Milgram’s small-world experiment showed that the average distance between any two people on Earth is six, and this phenomenon is referred to six degrees of separation [1, 2]. In 2011, the results of the analysis of the friend networks of 750 million active users in Facebook showed that the average distance between Facebook network nodes was only 4.74 degrees [3, 4]. In social network analysis, it is quite significant to find out or mining which node has the largest impact. Therefore, a lot of measurements have been proposed to calculate the importance of a node from different perspectives, including degree centrality, betweenness centrality, closeness centrality, k-shell centrality, eigenvector centrality, and the PageRank algorithm.Degree centrality was proposed by Professor Linton, which reflects local properties of the network, and the main consideration is the node itself and the neighbors properties. Although the calculation of degree centrality is simple, it has some deficiencies [5–7]. Betweenness centrality, closeness centrality, and eigenvector centrality reflect the global property [8] of networks. Among them, betweenness centrality [9, 10] mainly considered the shortest path through the node. Closeness centrality [11] measures the difficulty to reach the other node. Eigenvector centrality [12, 13] mainly considered the status and prestige in the networks using the composition of the reputation of other nodes to reflect the influence of the node for the entire network. K-shell centrality reflects the nodes location within networks to measure node communication capacities [14, 15]. In addition, the PageRank algorithm [16] is also used to measure the impact of network nodes.Currently, the most measurements are based on statistical properties with the topology of the networks and do not take the impact of changes of mutual trust among the nodes during information dissemination into account. In this paper, a new scheme to measure the dynamic influence of the nodes in a social network is proposed. In this new scheme, the modification of node trust value during information propagation plays a significant role. Furthermore, the cumulative change of nodes trust value is also considered in the new scheme.


## 2. The Measure of Dynamic Influence

### 2.1. The Model of Information Dissemination

SI, SIS, SIR, and so forth [17, 18] were originally used to research the spread of disease [19–21]. In these networks, people and their relations are considered as node and edge, which can be represented by G=(V,E), where V is a set of nodes and E is the set of connected edges. All nodes can be divided into three categories: class S (susceptible) refers to those who do not get sick, but, because of the lack of immunity, they are susceptible to infection after contact with a sick sense; class I (infective) refers to those who had infectious disease and it can spread to class S members; and class R (removal) refers to isolation or the person who has the illness and immunity.In addition, suppose the number of nodes is constantλ, and each time the number of nodes to be removed is a constant proportion of the total number of μ. The average propagation period is 1/μ, The dissemination number is σ=λ/μ. Figure 1 shows the procedure from susceptible state to removal state.Figure 1
The process is shown for nodes from the susceptible to removal state.The SIR model is defined by following equation:(1)didt=λsi-ui,dsdt=-λsi,drdt=μi.If the SIR model is used to illustrate the information dissemination in networkG=(V,E), s is considered as a node that can receive information, i represents a node that has received information and has the ability to disseminate information, and r represents a node which has received information but does not have the ability to disseminate it.


### 2.2. The Measure of Node Dynamic Influence

In this section, to further investigate the relationship between the sender node and the receiver node in a complex network, the nodes are stratified according to their distance from the node of information source. The layered network is shown in Figure2.Figure 2
Layered network diagram.The dynamic influence index of a social networks is represented byI. Several rounds of information sources on the network node transmitting information are represented by k. In addition, the trust value t is the cumulative effect of the information spreading, where t represents the node that is a push message acceptance of the push message from a node, namely, trust, 0<t<1.In Figure2, node a is considered as the information source node, and node a disseminates information to a set of neighbors {b,c,d,e,f} with a certain probability. Node a and node c are connected by edge Pac; tac is the trust value on edge Pac. When variable k changes, the value of t is also changed. This feature can be considered as a dynamic influence.UseVc to represent the number of once valid pushing and Vc′ to represent the number of once invalid pushing; tk,Ppq representing the trust value on edge Ppq of any two nodes p and q in the networks at k–rounds of dissemination, then the t value is(2)tk,Ppq=Vck,PpqVck,Ppq+Vc′k,PpqThe values of Vc at k–rounds and (k+1)–rounds of dissemination are(3)Vck+1,Ppq=Vck,Ppq+1,p∗d≥0.5Vck,Ppq,p∗d<0.5.Meanwhile,Vc′ value is calculated by(4)V′ck+1,Ppq=V′ck,Ppq+1,p∗d<0.5V′ck,Ppq,p∗d≥0.5.Ifp∗d<0.5, the edge of a message is an invalid recommendation, while p∗d≥0.5 means that there is a valid recommendation in (3) and (4), where p is the probability of the current node to propagate the message to its neighbor class S nodes and d is the number of neighbor node of the current node. It is important to note that d represents outdegree in the directed network, while, in the undirected network, it denotes the degree of the node.Probabilityp is determined by the level of the node, the information lost during dissemination, and effects of cumulative history dissemination to the current dissemination. In Figure 2, according to the information attenuation principle, we can see that probability p is inversely proportional to variable l (when l≥1, the default value l for each node is 1). L indicates the distance of the current node to source node. Probability p is also inversely proportional to c (when c≥0, the default value c for each node is 0), which indicates the number of times that network information dissemination process. Probability p is proportional to trust t, which derived from edge connected the current node and its parent node.The definition of probabilityp is as shown in(5)p=1c∗l2,c≥1,l≥1,0≤t<α1c∗l2∗1+α-t,c≥1,l≥1,0.5≤α<t<1.It is apparent that probabilityp decreases when layer deceased according to (3). Here, a new variable α is introduced to balance and limit the value range of p value.Afterk-rounds of information dissemination, the number of edges is Pn, indicating the edge counts through the information route. In this case, the influence of source node a is defined as the following equation:(6)Ik=∑p,q=0Pntk,Pp,q,where (p,q)=0 denotes the edge count; Ik is the influence of the source node a after k–rounds of the information dissemination.


### 2.3. The Detail of the Algorithm

The new algorithm aims to explore the relationship between the influence of the social network nodes and accumulation effects of information transmission. In this section, the stabilization ofIk is used to eventually measure the influence of the node. A flow chart of the detailed algorithm is shown in Figure 3.Figure 3
The flow chart of dynamic influence of node.The spreading node selection algorithm consists of two parts: (1) when one node pushing a message, most of its neighbors havet value to trust it. (2) Choose one neighbor node to receive the information.The trade-offs oft value determine the value of probability p: a larger t indicates a larger p. In the algorithm, the algorithm selects the node who has the largest t value, which is t=max⁡{t1,t2,…,tn}.The push target node selection strategy is when a node has the ability to push messages selection inr neighbor nodes, push message in d neighbors, and select the maximum value of neighbor node t on the path of a push.


## 2.1. The Model of Information Dissemination

SI, SIS, SIR, and so forth [17, 18] were originally used to research the spread of disease [19–21]. In these networks, people and their relations are considered as node and edge, which can be represented by G=(V,E), where V is a set of nodes and E is the set of connected edges. All nodes can be divided into three categories: class S (susceptible) refers to those who do not get sick, but, because of the lack of immunity, they are susceptible to infection after contact with a sick sense; class I (infective) refers to those who had infectious disease and it can spread to class S members; and class R (removal) refers to isolation or the person who has the illness and immunity.In addition, suppose the number of nodes is constantλ, and each time the number of nodes to be removed is a constant proportion of the total number of μ. The average propagation period is 1/μ, The dissemination number is σ=λ/μ. Figure 1 shows the procedure from susceptible state to removal state.Figure 1
The process is shown for nodes from the susceptible to removal state.The SIR model is defined by following equation:(1)didt=λsi-ui,dsdt=-λsi,drdt=μi.If the SIR model is used to illustrate the information dissemination in networkG=(V,E), s is considered as a node that can receive information, i represents a node that has received information and has the ability to disseminate information, and r represents a node which has received information but does not have the ability to disseminate it.


## 2.2. The Measure of Node Dynamic Influence

In this section, to further investigate the relationship between the sender node and the receiver node in a complex network, the nodes are stratified according to their distance from the node of information source. The layered network is shown in Figure2.Figure 2
Layered network diagram.The dynamic influence index of a social networks is represented byI. Several rounds of information sources on the network node transmitting information are represented by k. In addition, the trust value t is the cumulative effect of the information spreading, where t represents the node that is a push message acceptance of the push message from a node, namely, trust, 0<t<1.In Figure2, node a is considered as the information source node, and node a disseminates information to a set of neighbors {b,c,d,e,f} with a certain probability. Node a and node c are connected by edge Pac; tac is the trust value on edge Pac. When variable k changes, the value of t is also changed. This feature can be considered as a dynamic influence.UseVc to represent the number of once valid pushing and Vc′ to represent the number of once invalid pushing; tk,Ppq representing the trust value on edge Ppq of any two nodes p and q in the networks at k–rounds of dissemination, then the t value is(2)tk,Ppq=Vck,PpqVck,Ppq+Vc′k,PpqThe values of Vc at k–rounds and (k+1)–rounds of dissemination are(3)Vck+1,Ppq=Vck,Ppq+1,p∗d≥0.5Vck,Ppq,p∗d<0.5.Meanwhile,Vc′ value is calculated by(4)V′ck+1,Ppq=V′ck,Ppq+1,p∗d<0.5V′ck,Ppq,p∗d≥0.5.Ifp∗d<0.5, the edge of a message is an invalid recommendation, while p∗d≥0.5 means that there is a valid recommendation in (3) and (4), where p is the probability of the current node to propagate the message to its neighbor class S nodes and d is the number of neighbor node of the current node. It is important to note that d represents outdegree in the directed network, while, in the undirected network, it denotes the degree of the node.Probabilityp is determined by the level of the node, the information lost during dissemination, and effects of cumulative history dissemination to the current dissemination. In Figure 2, according to the information attenuation principle, we can see that probability p is inversely proportional to variable l (when l≥1, the default value l for each node is 1). L indicates the distance of the current node to source node. Probability p is also inversely proportional to c (when c≥0, the default value c for each node is 0), which indicates the number of times that network information dissemination process. Probability p is proportional to trust t, which derived from edge connected the current node and its parent node.The definition of probabilityp is as shown in(5)p=1c∗l2,c≥1,l≥1,0≤t<α1c∗l2∗1+α-t,c≥1,l≥1,0.5≤α<t<1.It is apparent that probabilityp decreases when layer deceased according to (3). Here, a new variable α is introduced to balance and limit the value range of p value.Afterk-rounds of information dissemination, the number of edges is Pn, indicating the edge counts through the information route. In this case, the influence of source node a is defined as the following equation:(6)Ik=∑p,q=0Pntk,Pp,q,where (p,q)=0 denotes the edge count; Ik is the influence of the source node a after k–rounds of the information dissemination.


## 2.3. The Detail of the Algorithm

The new algorithm aims to explore the relationship between the influence of the social network nodes and accumulation effects of information transmission. In this section, the stabilization ofIk is used to eventually measure the influence of the node. A flow chart of the detailed algorithm is shown in Figure 3.Figure 3
The flow chart of dynamic influence of node.The spreading node selection algorithm consists of two parts: (1) when one node pushing a message, most of its neighbors havet value to trust it. (2) Choose one neighbor node to receive the information.The trade-offs oft value determine the value of probability p: a larger t indicates a larger p. In the algorithm, the algorithm selects the node who has the largest t value, which is t=max⁡{t1,t2,…,tn}.The push target node selection strategy is when a node has the ability to push messages selection inr neighbor nodes, push message in d neighbors, and select the maximum value of neighbor node t on the path of a push.


## 3. Simulation Results

The initial values of the coefficients in our simulation are set top=0.5, l=1, c=0, α=0.5, t=0.5. All the data are from the public database [22, 23] shown in Table 1.Table 1
Dataset source and dataset size.
Datasets Node count Edge count Description Facebook1 347 2519 Slavo Zitnik in social networking sites Facebook friends relationship Twitter2 239 8120 1,367,531 nodes in Twitter social networks friends relationship Email3 1133 5451 Mr. Tsang communication contact record Blog4 10312 333983 The relationship between bloggers in Weibo BA 5000 49945 5000 nodes in a BA scale-free network 1Facebook: http://snap.stanford.edu/data/egonets-Facebook.html. 2Twitter: http://snap.stanford.edu/data/egonets-Twitter.html. 3Email: http://www.cs.bris.ac.uk/steve/neteworks/peacockpaper/. 4Blog: http://www.blogcatalog.com/.The dataset contains directed network, undirected networks, theoretical network, the real social networks, and the like. BA scale-free network [24] is a theoretical network that was proposed by Barabási and Albert to produce power-law distribution mechanism. It needs to specify that because the original online social network dataset contains isolated node, in this experiment, remove the original raw data collection network in the isolated node. In this experiment, the isolated nodes are removed in the original raw data collection network, and the maximum connectivity subgraph [25] is used in our simulations.In the simulations, the data of (|E|/|N|) are 7.2594, 33.9749, 4.8111, 32.3878, and 9.989, respectively. The simulation results are listed in Table 2. In Table 2, D represents an average degree [26] of the network, L is the average path length [27] of the network, ϕ is the density of the network [28], ρ is the density [29] of the network, W is the weighted average of the network, and C is the average clustering coefficient [30, 31] of the network.Table 2
The results of the statistical parameters of five network datasets.
Datasets D L ϕ ρ W C Facebook 15.129 3.752 11 0.046 15.129 0.508 Twitter 33.975 2.096 7 0.143 33.975 0.365 Email 11.559 1.992 3 0.01 28.79 0.526 Blog 64.776 2.382 5 0.006 0.238 0.463 BA 19.978 2.922 4 0.004 19.978 0.017In Figure4, we selected the highest ranking node from the five network datasets. The ranking is according to the dynamic influence of 1000-round dissemination. In Figure 5, similarly, we selected the lowest ranking node from the five network datasets; the ranking is according to the dynamic influence of 1000-round dissemination. The horizontal axis is the number of dissemination rounds; the vertical axis is the trust value that represents the dynamic influence, where the actual results of trust were normalized so that the results of different networks can be compared in the same coordinate system.Figure 4
The changes of the dynamic influence of highest ranked node.Figure 5
The changes of the dynamic influence of the lowest ranking.In the Facebook network, number 67 node has the highest influence, which is rising rapidly within 100 rounds of the dissemination phase. The influence of node number 67 increases slowly within 100 rounds to 200 rounds of the dissemination phase. Finally, stable dissemination occurs at approximately 400 rounds, and the trust value is 0.7911. Node number 157 has a very low influence and is slightly jittery within 50 rounds of the dissemination phase. The influence of node number 157 rapidly declines within 50 rounds to 200 rounds of the dissemination phase. Finally, stable dissemination occurs at approximately 784, with trust value 0.355.According to the simulation results, we can see that although different networks have different statistical properties, they have a same pattern, and the node with the highest influence increases quickly when the amount of dissemination increased and became eventually stable at approximately 300 rounds. For the nodes with low influence, they decreased faster and became eventually stable at approximately 500 rounds.In addition, the proposed algorithm (DI) is compared to degree centrality (DC), betweeness centrality (BC), closeness centrality (CC), eigenvector centrality (EC), and PageRank (PR) to verify the accuracy and validity of the algorithm.In Table3, the top four nodes are listed according to the different measure algorithms. The results are roughly the same. Finally, 10% of the nodes herein formerly had importance under each dataset used for analysis and comparison, as shown in Table 4.Table 3
The top four nodes under several algorithms.
Datasets Rank DC CC BC EC PR DI Facebook 1 56 277 277 56 25 67 2 67 25 175 67 56 56 3 271 322 19 271 67 271 4 322 67 23 26 322 26  Twitter 1 67 67 67 69 8 67 2 47 47 144 67 2 175 3 175 175 69 84 121105 47 4 189 189 45 8 69 203  Email 1 105 333 333 105 105 105 2 333 23 105 16 23 333 3 16 105 23 196 333 42 4 23 42 578 42 41 23  Blog 1 176 10271 4839 176 10298 176 2 1226 10259 4375 233 10310 233 3 446 8859 8859 283 9997 446 4 645 10269 7806 371 10298 645  BA 1 3 3 3 3 3 3 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 20 8 20 8 20 8Table 4
Ranking hit rate in a variety of algorithms at the intersection and union.
Datasets I s e t I a l l I h i t U s e t U a l l U h i t Facebook 10 10 100% 55 55 100% Twitter 6 6 100% 62 65 95.38% Email 38 38 100% 182 182 100% Blog 157 135 85.99% 2320 2716 85.42% BA 395 378 95.70% 610 645 94.57%In the Facebook network,Iset represents a collection of 10 elements under the five classical algorithms jointly that determined the top 10% nodes; Iall represents together with DC algorithm the top 10% to 10 nodes, namely, the intersection hits: Ihit = 100%. Similarly, Uset represents the union top 10% nodes under the five classical algorithms and the number of elements in the set is 55; Uall represents the union together with DC algorithm in the top 10%, which is set as hits, Uhit = 100%. Simulation results show that the proposed algorithm has good accuracy and effectiveness.


## 4. Conclusion

In this paper, a new judgment scheme on the dynamic influence of the social network nodes is proposed. Considering the effect of changes in the information dissemination process of trust values, a new measurement of node dynamic influence is proposed. It is an improvement of the traditional algorithms. Finally, we analyze the influence of nodes according to topology of the network or statistical properties and further compare it with several classical algorithms to verify the validity and accuracy of the algorithm.



---

*Source: 5046905-2017-01-31.xml*