# Novel Node Centrality-Based Efficient Empirical Robustness Assessment for Directed Network

Authors: Xiaolong Deng; Hao Ding; Yong Chen; Cai Chen; Tiejun Lv
Journal: Complexity
 (2020)

---

## Abstract

In recent years, while extensive researches on various networks properties have been proposed and accomplished, little has been proposed and done on network robustness and node vulnerability assessment under cascades in directed large-scale online community networks. In essential, an online directed social network is a group-centered and information spread-dominated online platform which is very different from the traditional undirected social network. Some further research studies have indicated that the online social network has high robustness to random removals of nodes but fails to the intentional attacks, particularly to those attacks based on node betweenness or node directed coefficient. To explore on the robustness of directed social network, in this article, we have proposed two novel node centralities ofITG (information transfer gain-based probability clustering coefficient) and IMpv (directed path-based node importance centrality). These two new centrality models are designed to capture this cascading effect in directed online social networks. Furthermore, we also propose a new and highly efficient computing method based on iterations for IMpv. Then, with the abundant experiments on the synthetic signed network and real-life networks derived from directed online social media and directed human mobile phone calling network, it has been proved that our ITG and IMpv based on directed social network robustness and node vulnerability assessment method is more accurate, efficient, and faster than several traditional centrality methods such as degree and betweenness. And we also have proposed the solid reasoning and proof process of iteration times k in computation of IMpv. To the best knowledge of us, our research has drawn some new light on the leading edge of robustness on the directed social network.


---

## Body

## 1. Introduction

With rapid increasing online social network, the network structure of online social networks has become more complicated than before. Analysis and explaining the dynamics and properties of social networks has become an interesting researching task with plenty of applications in social sciences and many other web application scripts. In some social networks, it is very common for some users who decide to leave the network or begin to stop being active in the activities of their community [1]. This phenomenon is also called as quitting or churn and has absorbed much research attention in social networks. And how to analyze and evaluate network robustness and resilience [2–4] after node departure or removal [5] has always been the hot research points [2, 6] in the last decade. And online social network has been classified as a scale-free network for demonstrating the power-law [7] distribution of degree by many famous complex network scientists [4, 8].Some recent research results have also told us that network nodes which have a large betweenness [8] value are closely related to swift information and material dissemination in a graph [9, 10] which is useful for quick network robustness and node vulnerability assessment. Because the traditional network robustness and node vulnerability assessment theories are based on undirected and nonweighted networks, it is necessary to research on the relationship of resilience of directed social network after node departure and the latest found rules of complex network which can be found in Figure 1 for Toy example. And it would be helpful to find some new discipline and cast new light on robustness and vulnerability assessment of directed social network.Figure 1
Toy example figure.In detail, our contributions are as follows:(1)
Basing on classic probability graph theory and clustering coefficient definition, we have proposed two new node centralities namedITG (information transfer gain) and IMpv (directed node importance). It can be used to measure the robustness and vulnerability in directed networks especially directed social networks which have been seldom tested before.(2)
We have proposed enough experiment results on undirected artificial networks and directed online social networks to make robustness assessment comparison ofITG and IMpv, which was mentioned scarcely in former-related works.(3)
OurITG- and IMpv-based centrality has been proved to be more accurate, efficient, and faster than classical centrality methods such as degree and betweenness with sufficient experiments results for node robustness assessment in directed social networks.(4)
We have firstly proposed a new rigorous proving process of directed node importance centralityIMpv and its implementation method. We have found that, in the more densely connected directed social network, the IMpv node removal strategy is the most harmful to the network connecting structure. And to the best knowledge of us, we attain the varying trend of iteration times k to the marginal difference ε on directed social networks for the first time based on strict mathematical proof.The outline of the paper is as follows: Section2 introduces the related work on robustness and resilience of scale-free network which includes some traditional complex network and social network. Section 3 presents the definitions of network structure quantities which we used to evaluate the robustness and vulnerability of network datasets. And our novel ITG- and IMpv-based directed node centrality will be introduced. Section 4 proposes the experiments results in synthetic signed network and real-life large networks derived from directed online social media and directed human mobile phone calling network with former undirected node centrality measures and our directed ITG centrality measure and IMpv. Section 5 gives the final conclusion of this article and draws some new light on the future work.


## 2. Related Work on Network Robustness

There have been many important research studies on vulnerability assessment and robustness assessment in network structures [11, 12] after node departure or network attack and other significant research areas.The robustness of ER random network and BA scale-free network was analyzed firstly by Albert [13] in 2000. He used the multiple correlation relationship data of l−1 (inverse geodesic length), S (size of the largest connected subgraph), and removed node ration under node attack to make vulnerability and robustness assessment. He discovered that collapse of scale-free network may reach a high price because of the selection and removal of a few nodes which play an important role in maintaining the connectivity of network.Also, in 2000, Cohen and Callaway [10, 14] observed that real networks demonstrating power-law degree distribution are robust against random node removal but easy to crash in case of attacks to high-degree nodes.Holme et al. [8] used four different removal strategies which will be introduced in Section 4 in 2002, and he found details of the response of networks according to these attacks on vertices and edges. Holme and his research team observed that the removals by the recalculated degrees and betweenness centralities are always more harmful than the attack strategies based on degrees and betweenness centralities of the initial network. But they only use one real communication network and did not propose some application points.Then, some researchers have discovered a few valuable results on directed networks. Xu and Wang [6] have done some experiments on the cascading crash on weighted complex networks in 2008. Newman and Ghoshal [2] found that removal of some special single node in the network may cause the bicomponents in the graph to be disconnected.Malliaros and Vazirgiannis [4] proposed a model to capture this cascading effect node departure of social network, based on engagement dynamics of social networks in 2015. Fragkiskos introduced a new concept of robustness assessment method under cascades triggered by the quitting of nodes based on their engagement level. His results indicated that social networks are very robust and strong under cascades triggered by randomly selected nodes but highly vulnerable in cascades caused by targeted departures of nodes with high engagement level.In 2016, Gao et al. [10] developed a set of analytical tools with which to identify the natural control and state parameters of a multidimensional complex system for stimulation, and it can attain effective one-dimensional dynamics that can accurately predict the system’s resilience. Their proposed analytical framework tool can systematically separate the roles of the system’s dynamics and topology, collapsing the behavior of different networks onto a single universal resilience function.But in the related research mentioned above, these researchers did not model on the information transfer process of directed social networks and cannot fulfill the network robustness and vulnerability assessment requirement of directed social networks nowadays, and it needs to construct some new model and methods to bridge the requirement gap in some efficient ways.


## 3. Definitions of Network Structure Quantities and Node Centrality Measures

In a scale-free network which includes undirected and directed ones, after some very important nodes are intentionally selected and removed, the network would suffer a serious collapse. It is necessary to research on the network resilience in directed networks, so we adopted three key performance quantitative indicators and some famous centralities indicators to make robust assessment of simulated and real networks.


### 3.1. Network Structure Quantitative Indicator Definition

In this paper, we used two types of network which are undirected and directed networks. On the one hand, for the undirected networks, the network model is unweighted and undirected, which can be demonstrated asG=V,E. V is the set of nodes with number N=V, and E is the set of edges with number L=E. On the other hand, the directed network model is always defined as G⟶=V,E with each edge having its own weight and direction to supply the directed vivid information and material spreading.


#### 3.1.1. Average Inverse Geodesic Length

In an undirected network, average inverse geodesic lengthl is the important network structure quantities after node failure. And in the directed network especially in social networks, the average inverse geodesic length l can be calculated by removal of the direction of edges:(1)l≡dv,w≡∑v∈V∑w≠v∈Vdv,w.In formula (1), dv,w stands for the geodesic path length between different nodes v and w. In traditional social networks of human relationship which is a small-world network, l is always around 6. In the new social networks such as Twitter and Facebook, it would decline to 4 which has been proved by Robert and Sebastiano in Laboratory for web algorithm [15] in 2015. After some nodes are removed, if there is no path between nodes v and w, dv,w would reach +∞. And there is another length quantity l−1 instead of l:(2)l−1≡dv,w≡1NN−1∑v∈V∑w≠v∈V1dv,w.The value of1/dv,w is zero where there does not exist path from node v to node w.


#### 3.1.2. Network Average Cluster Coefficient

In most network models, the node cluster coefficientCi reflects the density of connection around some focus nodes. In the whole network, the network average cluster coefficient CG=V,E demonstrates the macroscopically cluster characteristics of the whole network to reveal the density of links among neighbor nodes and the cluster coefficient of node can be found in the following formula:(3)Ci=2Eikiki−1,where ki stands for stands for the neighbor node number of node i and Ei stands for the actual number of existing links among neighbor nodes of node i. Network average cluster coefficient can be found in the following formula:(4)CG=V,E≡1N∑vi∈V,i=1N2Eikiki−1.


#### 3.1.3. Relative Size of Largest Connected Subgraph

In some disconnected large networks, there would exist some separated subgraphs and cannot connect to each other. Size of the largest connected subgraph is also called the node number of the largest connected subgraph in the whole graph which is important to reveal inner connectivity characteristics of graph. In the real network, it can assume that if the connected subgraphs set areg1,g2,g3,g4,……,gn in G=V,E, then definition of the relative size of the largest connected subgraph can be found in the following formula:(5)S=MaxVg1,Vg2,Vg3,……,VgnV.


### 3.2. Node Centrality Measures

In network, there are many node centrality measures to calculate the importance of node and each node has its own status and influence to its neighbors. Particularly, in the social relations network, it can demonstrate the relations among nodes. Based on node centrality measures, they can be used to analyze the closeness in the each other dependent relations between different nodes. Furthermore, node centrality measures can be used to calculate the role and graph position of every node for information dissemination influence analysis and other advancing applications [16–21]. Among these researches, node centrality is always the focus of analysis and research results of social network researchers [22] to find the role and status of node. Among these well-known node centralities, we have chosen three most common node centrality statistics and proposed two new node centrality measures which can be found as follows.


#### 3.2.1. Betweenness Centrality

Betweenness is a very famous and vital node centrality measure in network statistics computing. Its detailed definition is as follows: in graphG, if there exists a path between every node vi and vj while ∀vi,vj∈V,G is a connected graph and there must be a shortest graph to connect vi and vj which is always called the geodesic path. Thus, we can use the assuming shortest paths number between two vertices to quantify the importance of a vertex or an edge in terms of its betweenness centrality [23] which can be found in the following formula:(6)Bu=∑i,jσi,u,jσi,j.In formula (6), σi,u,j is the number of shortest paths between vertices vi and vj that pass through vertex u and σi,j is the total number of shortest paths between nodes vi and vj.


#### 3.2.2. PageRank Centrality

PageRank is a typical link analysis centrality measure invented by Larry Page in 1997 with the purpose of “calculating” its relative importance within the linking data set. And PageRank also can be applied to calculate node centrality. The simple definition of PageRank can be found in formula (7). In our calculation, damping factor d equals 0.85 as a constant value. The calculation formula of PageRank is as follows.When page number increases and the damping factor is used to recalculate the PageRank mark of every page, damping factor stands for the real mark when one page is linked to the other page with the range from zero to 1. In our calculation, the damping factor value equals 0.85 as a constant value. The calculation formula of PageRank is as follows:(7)PRA=1−d+dPRt1Ct1+⋯+PRtnCtn.In formula (7), PRt1 stands for PR (PageRank) marks in which t1 brings to page A (t1 is linked to A). In the same way, Ct1 stands for pages which are linked to page t1.


#### 3.2.3. Degree Centrality

In social network, the degree centrality is that central users have the most ties to other actors in the network. If the central user is more powerful and influential in the connecting network, it will have much more links to other users including in and out links. The number of adjacent edges a node has is defined as a degree. In graphG, if the degree of node vi is degvi and the total degree of nodes in the graph is ∑vi∈Vdegvi, the degree centrality of node vi is Dvi which defined in as follows [24]:(8)Dvi=degvi∑vi∈Vdegvi.From the definition above in formula (8), it can be found that node degree centrality expressed the ratio of degree of the node u to the total degree in the whole graph and some nodes with a higher degree centrality reflect that this node may have some powerful role linking to other node in the network and it may be the most vital person living in the focus of attention.


#### 3.2.4. Directed Path-Based Node Importance Centrality

With the rapid development of information technology, our life is becoming more and more networked. The graph information is closely related to our daily life, such as the directed WeChat relation network and directed Facebook relation network with such complex structures. And most important of all is that the scale of these graphs is enormous and it is hard to handle these so complex and massive graphs. In a directed graph network, how to quantitatively analyze and calculate the importance of each vertex has become an important problem to be solved urgently for those directed graph networks, while they all have some common features [25, 26]. Among these statistical indicators for directed graph networks, directed path-based directed node importance centrality has become more prominent for its easy and fast calculation.In the directed graph networkG, if there exists a path ei=vi,vj between nodes vi and vj, directed path-based directed node importance centrality of node vj can be expressed by the paths across node vj. The more the across paths are, the more important the node vj is. Directed path-based node importance centrality IMpv of node v has been posed in the famous book with the name “Computer Science Theory for the Information Age” by John Hopcroft and Kannan [27], but this book did not demonstrate some fast and efficient computing methods of IMpv which we have found in formula (9). And definition of directed path-based node importance centrality IMpv of node v can be found in formula as follows:(9)IMpv=Ipv+Opv=∑u∈IvIpu+∑u∈OvOpu.In formula (9), Ipv stands for the directed paths number which finally ends in node v where Iv=v|u,v∈E and Opv stands for the directed paths number which starts from node v where Ov=v|u,v∈E. Basing on formula (9), we can calculate the IMpv of nodes in directed networks when we solve two critical problems first. One problem is that, in complex structured graphs with huge number nodes, the time complexity of the iterative calculation will be very high and the other problem is that the convergence of the calculation process of formula (9) cannot be reached if we do not use some approximate calculation methods.ForIpv=∑u∈IvIpu in formula (9), it can be converted to iterative computation in the following formula:(10)Ipvk=∑u∈IvIpuk−1.In formula (10), Ipvk stands for the kth iteration calculation result, and for any node v, the initial value of Ipvk is Ipv0=1. For the reason that computation of formula (10) cannot converge by its diverging computation process, the iterative results of formula (10) need to be standardized in formula (11a) in which α is the damping factor with the value range of 0<α<1 just like the damping factor in the PageRank computation model:(11a)Ipvk=1−α+α⋅∑u∈IvIpuk−1∑u∈IvIpuk−12.For the similar computation principle, the standardized form ofOpv in formula (9) can be written as follows:(11b)Opvk=1−α+α⋅∑u∈IvOpuk−1∑u∈IvOpuk−12.In computation of formulas (11a) and (11b), we can use M to stand for the adjacency matrix of directed graph network G and Ip to stand for the vector composed by all the Ipv values of the node set v∈V in G while v=n. And Ip can be expressed by Ip=Ipv1,Ipv2,…,IpvnT, while formula (11a) can be changed as follows:(12a)Ip=1−α⋅I+α⋅M⋅IpM⋅Ip.In formula (12a), I=1,1,…,1T and Ip can be initialized to Ip=I. For the similar computation principle, formula (11b) can be changed as follows:(12b)Op=1−α⋅I+α⋅M⋅OpM⋅Op.By using formulas (12a) and (12b), the computation of directed path-based node importance centrality IMpv of node v can be transferred to the computation of adjacency matrix M of directed graph network G with great promotion. Furthermore, we will demonstrate the whole proof process which using the Power Iteration Theory [28] to prove that formulas (12a) and (12b) can converge to a definite vector by finite times of computations. For the adjacency matrix M=mij∈Rn∗n of directed graph network G, it has the eigenvalue set of λ1,…,λnλi∈R, while λ1>λ2≥⋯≥λn and λ1=1. At the same time, Mxi=λixi and eigenvectors set ⟶xii=1,…,n can satisfy that ⟶xi⋅⟶xj=0i≠j.We can assure thaty0=∑i=0ncixi and yk can be expressed as yk=∑i=0nciλikxi.Here, [y0,y1,…,yk] can be used to replace Ip=Ipv1,Ipv2,…,IpvnT or Op=Opv1,Opv2,…,Opvn for formulas (11a) and (11b).Foryi∈y0,y1,…,yk, 0≤i<k,(13a)yk+1−yk=∑i=1nciλik+1xi−∑i=1nciλikxi=∑i=2nciλikλi−1xi≤∑i=2nciλikλi−1xi≤n−1cmaxλ2−1λ2kximax≤aλ2k,where a>0,a=n−1cmaxλ2−1ximax.We can also prove that the iteration timesk (k = [1, N] of computation for yk+1−yk) are around a constant level value in the following formula:(13b)∀yk+1−yk<ε⟹aλ2k<ε0<ε<1⟹klogλ2<logε−loga⟹k>logε−logalogλ2.And the constant level value ofk is(13c)k>ηlogε+βη<0,η=1logλ2,β=−logalogλ2.


#### 3.2.5.ITG-Based Directed Node Centrality

In most actual social networks such as Twitter, Facebook, and WeChat, the two friends of someone can be friends with each other. And this phenomenon can be found in both undirected networks and directed networks. So this attribute of social networks sometimes is called the clustering characteristic of network [7]. Network average clustering coefficient reflects the microscopically clustering characteristic of network and has become the very important measure of adjacent nodes which are connected closely. The definition of network node clustering coefficient can be found in Section 3.1.2. Based on the classic probabilistic graphical model (PGM) theory from Turing Award Owner Pearl [29], we have made a detailed research on directed node influence clustering coefficient [30] to propose a new vector influence clustering coefficient model with both information propagation direction and information propagation probability. The new vector influence clustering coefficient model starts from the two basic directed triple forms of vertex i in the directed graph which can be found in Figure 2.Figure 2
Two triple forms of vertexi in undirected graph.
(a)(b)Basing on deducting from Figures2(a) and 2(b), we can get the related edge information propagation probability and direction of different two types including 36 subgraphs of all different triples [30]. And then we can calculate all numerical values of directed ITG node centrality in directed social networks in all kinds of situations by the following formula:(14)∑ITGi⟷j=ITGi⟷j+ITGi⟷k⟷j=ITGi⟷j+ITGi⟷k+ITGk⟷j,(15)∑ITGi⟷k=ITGi⟷k+ITGi⟷j+ITGj⟷k.Because there are three possible directional statuses for each edge in Figures2(a) and 2(b), the adjacent edge of node i has three different definitions, which are friends relationship (i⟷j), following relationship (i⟶j), and fan relationship (i⟵j). At the same time, the opposite edge i⟷k of node i also has three definitions. Furthermore, the edge j⟷k has three types of relationships, in which node j and node k are friends, node j follows node k, and node k follows node j. We can use 0, 1, and 2 to stand for the relationships and substitute the three different definitions, and we obtain the following 27 arrangements in Table 1 [30].Table 1
Permutation and combination of 27 conditions.
000001002010011012020021022100101102110111112120121122200201202210211212220221222In the above 27 arrangement cases, because nodei is the source node, we can find some symmetry results, and finally, we can get 15 independent results. And the ITG-based directed node centrality value from information transfer gain clustering coefficient (ITGC) of node i in a directed network can be finally summed by the 15 different independent results in formula (16) as follows:(16)ITGCi=∑t=115ITGi_trianglet×Numbert∑t′=16ITGi_triplet′×Numbert′.ITGCi is the ITG value of node i in a directed network. ∑t=115ITGi_trianglet×Numbert is the weighted number of triangles which use node i as the top vertex (i.e., the information transfer source node), and its weight is the ITG (information transfer gain) contribution ITGi_trianglet from the 15 different types of weighted triangles multiplied by its counted number Numbert. ∑t′=16ITGi_triplet′×Numbert′ is the weighted number of the triples using node i as the top vertex; its weight is the weighted sum of the six ITGi_triplet′ values of different types of triples multiplied by its counted number Numbert′. Similar to undirected clustering coefficients, ITGC has the same characteristic, measuring the tightness of the graph to form tight communities.


## 3.1. Network Structure Quantitative Indicator Definition

In this paper, we used two types of network which are undirected and directed networks. On the one hand, for the undirected networks, the network model is unweighted and undirected, which can be demonstrated asG=V,E. V is the set of nodes with number N=V, and E is the set of edges with number L=E. On the other hand, the directed network model is always defined as G⟶=V,E with each edge having its own weight and direction to supply the directed vivid information and material spreading.


### 3.1.1. Average Inverse Geodesic Length

In an undirected network, average inverse geodesic lengthl is the important network structure quantities after node failure. And in the directed network especially in social networks, the average inverse geodesic length l can be calculated by removal of the direction of edges:(1)l≡dv,w≡∑v∈V∑w≠v∈Vdv,w.In formula (1), dv,w stands for the geodesic path length between different nodes v and w. In traditional social networks of human relationship which is a small-world network, l is always around 6. In the new social networks such as Twitter and Facebook, it would decline to 4 which has been proved by Robert and Sebastiano in Laboratory for web algorithm [15] in 2015. After some nodes are removed, if there is no path between nodes v and w, dv,w would reach +∞. And there is another length quantity l−1 instead of l:(2)l−1≡dv,w≡1NN−1∑v∈V∑w≠v∈V1dv,w.The value of1/dv,w is zero where there does not exist path from node v to node w.


### 3.1.2. Network Average Cluster Coefficient

In most network models, the node cluster coefficientCi reflects the density of connection around some focus nodes. In the whole network, the network average cluster coefficient CG=V,E demonstrates the macroscopically cluster characteristics of the whole network to reveal the density of links among neighbor nodes and the cluster coefficient of node can be found in the following formula:(3)Ci=2Eikiki−1,where ki stands for stands for the neighbor node number of node i and Ei stands for the actual number of existing links among neighbor nodes of node i. Network average cluster coefficient can be found in the following formula:(4)CG=V,E≡1N∑vi∈V,i=1N2Eikiki−1.


### 3.1.3. Relative Size of Largest Connected Subgraph

In some disconnected large networks, there would exist some separated subgraphs and cannot connect to each other. Size of the largest connected subgraph is also called the node number of the largest connected subgraph in the whole graph which is important to reveal inner connectivity characteristics of graph. In the real network, it can assume that if the connected subgraphs set areg1,g2,g3,g4,……,gn in G=V,E, then definition of the relative size of the largest connected subgraph can be found in the following formula:(5)S=MaxVg1,Vg2,Vg3,……,VgnV.


## 3.1.1. Average Inverse Geodesic Length

In an undirected network, average inverse geodesic lengthl is the important network structure quantities after node failure. And in the directed network especially in social networks, the average inverse geodesic length l can be calculated by removal of the direction of edges:(1)l≡dv,w≡∑v∈V∑w≠v∈Vdv,w.In formula (1), dv,w stands for the geodesic path length between different nodes v and w. In traditional social networks of human relationship which is a small-world network, l is always around 6. In the new social networks such as Twitter and Facebook, it would decline to 4 which has been proved by Robert and Sebastiano in Laboratory for web algorithm [15] in 2015. After some nodes are removed, if there is no path between nodes v and w, dv,w would reach +∞. And there is another length quantity l−1 instead of l:(2)l−1≡dv,w≡1NN−1∑v∈V∑w≠v∈V1dv,w.The value of1/dv,w is zero where there does not exist path from node v to node w.


## 3.1.2. Network Average Cluster Coefficient

In most network models, the node cluster coefficientCi reflects the density of connection around some focus nodes. In the whole network, the network average cluster coefficient CG=V,E demonstrates the macroscopically cluster characteristics of the whole network to reveal the density of links among neighbor nodes and the cluster coefficient of node can be found in the following formula:(3)Ci=2Eikiki−1,where ki stands for stands for the neighbor node number of node i and Ei stands for the actual number of existing links among neighbor nodes of node i. Network average cluster coefficient can be found in the following formula:(4)CG=V,E≡1N∑vi∈V,i=1N2Eikiki−1.


## 3.1.3. Relative Size of Largest Connected Subgraph

In some disconnected large networks, there would exist some separated subgraphs and cannot connect to each other. Size of the largest connected subgraph is also called the node number of the largest connected subgraph in the whole graph which is important to reveal inner connectivity characteristics of graph. In the real network, it can assume that if the connected subgraphs set areg1,g2,g3,g4,……,gn in G=V,E, then definition of the relative size of the largest connected subgraph can be found in the following formula:(5)S=MaxVg1,Vg2,Vg3,……,VgnV.


## 3.2. Node Centrality Measures

In network, there are many node centrality measures to calculate the importance of node and each node has its own status and influence to its neighbors. Particularly, in the social relations network, it can demonstrate the relations among nodes. Based on node centrality measures, they can be used to analyze the closeness in the each other dependent relations between different nodes. Furthermore, node centrality measures can be used to calculate the role and graph position of every node for information dissemination influence analysis and other advancing applications [16–21]. Among these researches, node centrality is always the focus of analysis and research results of social network researchers [22] to find the role and status of node. Among these well-known node centralities, we have chosen three most common node centrality statistics and proposed two new node centrality measures which can be found as follows.


### 3.2.1. Betweenness Centrality

Betweenness is a very famous and vital node centrality measure in network statistics computing. Its detailed definition is as follows: in graphG, if there exists a path between every node vi and vj while ∀vi,vj∈V,G is a connected graph and there must be a shortest graph to connect vi and vj which is always called the geodesic path. Thus, we can use the assuming shortest paths number between two vertices to quantify the importance of a vertex or an edge in terms of its betweenness centrality [23] which can be found in the following formula:(6)Bu=∑i,jσi,u,jσi,j.In formula (6), σi,u,j is the number of shortest paths between vertices vi and vj that pass through vertex u and σi,j is the total number of shortest paths between nodes vi and vj.


### 3.2.2. PageRank Centrality

PageRank is a typical link analysis centrality measure invented by Larry Page in 1997 with the purpose of “calculating” its relative importance within the linking data set. And PageRank also can be applied to calculate node centrality. The simple definition of PageRank can be found in formula (7). In our calculation, damping factor d equals 0.85 as a constant value. The calculation formula of PageRank is as follows.When page number increases and the damping factor is used to recalculate the PageRank mark of every page, damping factor stands for the real mark when one page is linked to the other page with the range from zero to 1. In our calculation, the damping factor value equals 0.85 as a constant value. The calculation formula of PageRank is as follows:(7)PRA=1−d+dPRt1Ct1+⋯+PRtnCtn.In formula (7), PRt1 stands for PR (PageRank) marks in which t1 brings to page A (t1 is linked to A). In the same way, Ct1 stands for pages which are linked to page t1.


### 3.2.3. Degree Centrality

In social network, the degree centrality is that central users have the most ties to other actors in the network. If the central user is more powerful and influential in the connecting network, it will have much more links to other users including in and out links. The number of adjacent edges a node has is defined as a degree. In graphG, if the degree of node vi is degvi and the total degree of nodes in the graph is ∑vi∈Vdegvi, the degree centrality of node vi is Dvi which defined in as follows [24]:(8)Dvi=degvi∑vi∈Vdegvi.From the definition above in formula (8), it can be found that node degree centrality expressed the ratio of degree of the node u to the total degree in the whole graph and some nodes with a higher degree centrality reflect that this node may have some powerful role linking to other node in the network and it may be the most vital person living in the focus of attention.


### 3.2.4. Directed Path-Based Node Importance Centrality

With the rapid development of information technology, our life is becoming more and more networked. The graph information is closely related to our daily life, such as the directed WeChat relation network and directed Facebook relation network with such complex structures. And most important of all is that the scale of these graphs is enormous and it is hard to handle these so complex and massive graphs. In a directed graph network, how to quantitatively analyze and calculate the importance of each vertex has become an important problem to be solved urgently for those directed graph networks, while they all have some common features [25, 26]. Among these statistical indicators for directed graph networks, directed path-based directed node importance centrality has become more prominent for its easy and fast calculation.In the directed graph networkG, if there exists a path ei=vi,vj between nodes vi and vj, directed path-based directed node importance centrality of node vj can be expressed by the paths across node vj. The more the across paths are, the more important the node vj is. Directed path-based node importance centrality IMpv of node v has been posed in the famous book with the name “Computer Science Theory for the Information Age” by John Hopcroft and Kannan [27], but this book did not demonstrate some fast and efficient computing methods of IMpv which we have found in formula (9). And definition of directed path-based node importance centrality IMpv of node v can be found in formula as follows:(9)IMpv=Ipv+Opv=∑u∈IvIpu+∑u∈OvOpu.In formula (9), Ipv stands for the directed paths number which finally ends in node v where Iv=v|u,v∈E and Opv stands for the directed paths number which starts from node v where Ov=v|u,v∈E. Basing on formula (9), we can calculate the IMpv of nodes in directed networks when we solve two critical problems first. One problem is that, in complex structured graphs with huge number nodes, the time complexity of the iterative calculation will be very high and the other problem is that the convergence of the calculation process of formula (9) cannot be reached if we do not use some approximate calculation methods.ForIpv=∑u∈IvIpu in formula (9), it can be converted to iterative computation in the following formula:(10)Ipvk=∑u∈IvIpuk−1.In formula (10), Ipvk stands for the kth iteration calculation result, and for any node v, the initial value of Ipvk is Ipv0=1. For the reason that computation of formula (10) cannot converge by its diverging computation process, the iterative results of formula (10) need to be standardized in formula (11a) in which α is the damping factor with the value range of 0<α<1 just like the damping factor in the PageRank computation model:(11a)Ipvk=1−α+α⋅∑u∈IvIpuk−1∑u∈IvIpuk−12.For the similar computation principle, the standardized form ofOpv in formula (9) can be written as follows:(11b)Opvk=1−α+α⋅∑u∈IvOpuk−1∑u∈IvOpuk−12.In computation of formulas (11a) and (11b), we can use M to stand for the adjacency matrix of directed graph network G and Ip to stand for the vector composed by all the Ipv values of the node set v∈V in G while v=n. And Ip can be expressed by Ip=Ipv1,Ipv2,…,IpvnT, while formula (11a) can be changed as follows:(12a)Ip=1−α⋅I+α⋅M⋅IpM⋅Ip.In formula (12a), I=1,1,…,1T and Ip can be initialized to Ip=I. For the similar computation principle, formula (11b) can be changed as follows:(12b)Op=1−α⋅I+α⋅M⋅OpM⋅Op.By using formulas (12a) and (12b), the computation of directed path-based node importance centrality IMpv of node v can be transferred to the computation of adjacency matrix M of directed graph network G with great promotion. Furthermore, we will demonstrate the whole proof process which using the Power Iteration Theory [28] to prove that formulas (12a) and (12b) can converge to a definite vector by finite times of computations. For the adjacency matrix M=mij∈Rn∗n of directed graph network G, it has the eigenvalue set of λ1,…,λnλi∈R, while λ1>λ2≥⋯≥λn and λ1=1. At the same time, Mxi=λixi and eigenvectors set ⟶xii=1,…,n can satisfy that ⟶xi⋅⟶xj=0i≠j.We can assure thaty0=∑i=0ncixi and yk can be expressed as yk=∑i=0nciλikxi.Here, [y0,y1,…,yk] can be used to replace Ip=Ipv1,Ipv2,…,IpvnT or Op=Opv1,Opv2,…,Opvn for formulas (11a) and (11b).Foryi∈y0,y1,…,yk, 0≤i<k,(13a)yk+1−yk=∑i=1nciλik+1xi−∑i=1nciλikxi=∑i=2nciλikλi−1xi≤∑i=2nciλikλi−1xi≤n−1cmaxλ2−1λ2kximax≤aλ2k,where a>0,a=n−1cmaxλ2−1ximax.We can also prove that the iteration timesk (k = [1, N] of computation for yk+1−yk) are around a constant level value in the following formula:(13b)∀yk+1−yk<ε⟹aλ2k<ε0<ε<1⟹klogλ2<logε−loga⟹k>logε−logalogλ2.And the constant level value ofk is(13c)k>ηlogε+βη<0,η=1logλ2,β=−logalogλ2.


### 3.2.5.ITG-Based Directed Node Centrality

In most actual social networks such as Twitter, Facebook, and WeChat, the two friends of someone can be friends with each other. And this phenomenon can be found in both undirected networks and directed networks. So this attribute of social networks sometimes is called the clustering characteristic of network [7]. Network average clustering coefficient reflects the microscopically clustering characteristic of network and has become the very important measure of adjacent nodes which are connected closely. The definition of network node clustering coefficient can be found in Section 3.1.2. Based on the classic probabilistic graphical model (PGM) theory from Turing Award Owner Pearl [29], we have made a detailed research on directed node influence clustering coefficient [30] to propose a new vector influence clustering coefficient model with both information propagation direction and information propagation probability. The new vector influence clustering coefficient model starts from the two basic directed triple forms of vertex i in the directed graph which can be found in Figure 2.Figure 2
Two triple forms of vertexi in undirected graph.
(a)(b)Basing on deducting from Figures2(a) and 2(b), we can get the related edge information propagation probability and direction of different two types including 36 subgraphs of all different triples [30]. And then we can calculate all numerical values of directed ITG node centrality in directed social networks in all kinds of situations by the following formula:(14)∑ITGi⟷j=ITGi⟷j+ITGi⟷k⟷j=ITGi⟷j+ITGi⟷k+ITGk⟷j,(15)∑ITGi⟷k=ITGi⟷k+ITGi⟷j+ITGj⟷k.Because there are three possible directional statuses for each edge in Figures2(a) and 2(b), the adjacent edge of node i has three different definitions, which are friends relationship (i⟷j), following relationship (i⟶j), and fan relationship (i⟵j). At the same time, the opposite edge i⟷k of node i also has three definitions. Furthermore, the edge j⟷k has three types of relationships, in which node j and node k are friends, node j follows node k, and node k follows node j. We can use 0, 1, and 2 to stand for the relationships and substitute the three different definitions, and we obtain the following 27 arrangements in Table 1 [30].Table 1
Permutation and combination of 27 conditions.
000001002010011012020021022100101102110111112120121122200201202210211212220221222In the above 27 arrangement cases, because nodei is the source node, we can find some symmetry results, and finally, we can get 15 independent results. And the ITG-based directed node centrality value from information transfer gain clustering coefficient (ITGC) of node i in a directed network can be finally summed by the 15 different independent results in formula (16) as follows:(16)ITGCi=∑t=115ITGi_trianglet×Numbert∑t′=16ITGi_triplet′×Numbert′.ITGCi is the ITG value of node i in a directed network. ∑t=115ITGi_trianglet×Numbert is the weighted number of triangles which use node i as the top vertex (i.e., the information transfer source node), and its weight is the ITG (information transfer gain) contribution ITGi_trianglet from the 15 different types of weighted triangles multiplied by its counted number Numbert. ∑t′=16ITGi_triplet′×Numbert′ is the weighted number of the triples using node i as the top vertex; its weight is the weighted sum of the six ITGi_triplet′ values of different types of triples multiplied by its counted number Numbert′. Similar to undirected clustering coefficients, ITGC has the same characteristic, measuring the tightness of the graph to form tight communities.


## 3.2.1. Betweenness Centrality

Betweenness is a very famous and vital node centrality measure in network statistics computing. Its detailed definition is as follows: in graphG, if there exists a path between every node vi and vj while ∀vi,vj∈V,G is a connected graph and there must be a shortest graph to connect vi and vj which is always called the geodesic path. Thus, we can use the assuming shortest paths number between two vertices to quantify the importance of a vertex or an edge in terms of its betweenness centrality [23] which can be found in the following formula:(6)Bu=∑i,jσi,u,jσi,j.In formula (6), σi,u,j is the number of shortest paths between vertices vi and vj that pass through vertex u and σi,j is the total number of shortest paths between nodes vi and vj.


## 3.2.2. PageRank Centrality

PageRank is a typical link analysis centrality measure invented by Larry Page in 1997 with the purpose of “calculating” its relative importance within the linking data set. And PageRank also can be applied to calculate node centrality. The simple definition of PageRank can be found in formula (7). In our calculation, damping factor d equals 0.85 as a constant value. The calculation formula of PageRank is as follows.When page number increases and the damping factor is used to recalculate the PageRank mark of every page, damping factor stands for the real mark when one page is linked to the other page with the range from zero to 1. In our calculation, the damping factor value equals 0.85 as a constant value. The calculation formula of PageRank is as follows:(7)PRA=1−d+dPRt1Ct1+⋯+PRtnCtn.In formula (7), PRt1 stands for PR (PageRank) marks in which t1 brings to page A (t1 is linked to A). In the same way, Ct1 stands for pages which are linked to page t1.


## 3.2.3. Degree Centrality

In social network, the degree centrality is that central users have the most ties to other actors in the network. If the central user is more powerful and influential in the connecting network, it will have much more links to other users including in and out links. The number of adjacent edges a node has is defined as a degree. In graphG, if the degree of node vi is degvi and the total degree of nodes in the graph is ∑vi∈Vdegvi, the degree centrality of node vi is Dvi which defined in as follows [24]:(8)Dvi=degvi∑vi∈Vdegvi.From the definition above in formula (8), it can be found that node degree centrality expressed the ratio of degree of the node u to the total degree in the whole graph and some nodes with a higher degree centrality reflect that this node may have some powerful role linking to other node in the network and it may be the most vital person living in the focus of attention.


## 3.2.4. Directed Path-Based Node Importance Centrality

With the rapid development of information technology, our life is becoming more and more networked. The graph information is closely related to our daily life, such as the directed WeChat relation network and directed Facebook relation network with such complex structures. And most important of all is that the scale of these graphs is enormous and it is hard to handle these so complex and massive graphs. In a directed graph network, how to quantitatively analyze and calculate the importance of each vertex has become an important problem to be solved urgently for those directed graph networks, while they all have some common features [25, 26]. Among these statistical indicators for directed graph networks, directed path-based directed node importance centrality has become more prominent for its easy and fast calculation.In the directed graph networkG, if there exists a path ei=vi,vj between nodes vi and vj, directed path-based directed node importance centrality of node vj can be expressed by the paths across node vj. The more the across paths are, the more important the node vj is. Directed path-based node importance centrality IMpv of node v has been posed in the famous book with the name “Computer Science Theory for the Information Age” by John Hopcroft and Kannan [27], but this book did not demonstrate some fast and efficient computing methods of IMpv which we have found in formula (9). And definition of directed path-based node importance centrality IMpv of node v can be found in formula as follows:(9)IMpv=Ipv+Opv=∑u∈IvIpu+∑u∈OvOpu.In formula (9), Ipv stands for the directed paths number which finally ends in node v where Iv=v|u,v∈E and Opv stands for the directed paths number which starts from node v where Ov=v|u,v∈E. Basing on formula (9), we can calculate the IMpv of nodes in directed networks when we solve two critical problems first. One problem is that, in complex structured graphs with huge number nodes, the time complexity of the iterative calculation will be very high and the other problem is that the convergence of the calculation process of formula (9) cannot be reached if we do not use some approximate calculation methods.ForIpv=∑u∈IvIpu in formula (9), it can be converted to iterative computation in the following formula:(10)Ipvk=∑u∈IvIpuk−1.In formula (10), Ipvk stands for the kth iteration calculation result, and for any node v, the initial value of Ipvk is Ipv0=1. For the reason that computation of formula (10) cannot converge by its diverging computation process, the iterative results of formula (10) need to be standardized in formula (11a) in which α is the damping factor with the value range of 0<α<1 just like the damping factor in the PageRank computation model:(11a)Ipvk=1−α+α⋅∑u∈IvIpuk−1∑u∈IvIpuk−12.For the similar computation principle, the standardized form ofOpv in formula (9) can be written as follows:(11b)Opvk=1−α+α⋅∑u∈IvOpuk−1∑u∈IvOpuk−12.In computation of formulas (11a) and (11b), we can use M to stand for the adjacency matrix of directed graph network G and Ip to stand for the vector composed by all the Ipv values of the node set v∈V in G while v=n. And Ip can be expressed by Ip=Ipv1,Ipv2,…,IpvnT, while formula (11a) can be changed as follows:(12a)Ip=1−α⋅I+α⋅M⋅IpM⋅Ip.In formula (12a), I=1,1,…,1T and Ip can be initialized to Ip=I. For the similar computation principle, formula (11b) can be changed as follows:(12b)Op=1−α⋅I+α⋅M⋅OpM⋅Op.By using formulas (12a) and (12b), the computation of directed path-based node importance centrality IMpv of node v can be transferred to the computation of adjacency matrix M of directed graph network G with great promotion. Furthermore, we will demonstrate the whole proof process which using the Power Iteration Theory [28] to prove that formulas (12a) and (12b) can converge to a definite vector by finite times of computations. For the adjacency matrix M=mij∈Rn∗n of directed graph network G, it has the eigenvalue set of λ1,…,λnλi∈R, while λ1>λ2≥⋯≥λn and λ1=1. At the same time, Mxi=λixi and eigenvectors set ⟶xii=1,…,n can satisfy that ⟶xi⋅⟶xj=0i≠j.We can assure thaty0=∑i=0ncixi and yk can be expressed as yk=∑i=0nciλikxi.Here, [y0,y1,…,yk] can be used to replace Ip=Ipv1,Ipv2,…,IpvnT or Op=Opv1,Opv2,…,Opvn for formulas (11a) and (11b).Foryi∈y0,y1,…,yk, 0≤i<k,(13a)yk+1−yk=∑i=1nciλik+1xi−∑i=1nciλikxi=∑i=2nciλikλi−1xi≤∑i=2nciλikλi−1xi≤n−1cmaxλ2−1λ2kximax≤aλ2k,where a>0,a=n−1cmaxλ2−1ximax.We can also prove that the iteration timesk (k = [1, N] of computation for yk+1−yk) are around a constant level value in the following formula:(13b)∀yk+1−yk<ε⟹aλ2k<ε0<ε<1⟹klogλ2<logε−loga⟹k>logε−logalogλ2.And the constant level value ofk is(13c)k>ηlogε+βη<0,η=1logλ2,β=−logalogλ2.


## 3.2.5.ITG-Based Directed Node Centrality

In most actual social networks such as Twitter, Facebook, and WeChat, the two friends of someone can be friends with each other. And this phenomenon can be found in both undirected networks and directed networks. So this attribute of social networks sometimes is called the clustering characteristic of network [7]. Network average clustering coefficient reflects the microscopically clustering characteristic of network and has become the very important measure of adjacent nodes which are connected closely. The definition of network node clustering coefficient can be found in Section 3.1.2. Based on the classic probabilistic graphical model (PGM) theory from Turing Award Owner Pearl [29], we have made a detailed research on directed node influence clustering coefficient [30] to propose a new vector influence clustering coefficient model with both information propagation direction and information propagation probability. The new vector influence clustering coefficient model starts from the two basic directed triple forms of vertex i in the directed graph which can be found in Figure 2.Figure 2
Two triple forms of vertexi in undirected graph.
(a)(b)Basing on deducting from Figures2(a) and 2(b), we can get the related edge information propagation probability and direction of different two types including 36 subgraphs of all different triples [30]. And then we can calculate all numerical values of directed ITG node centrality in directed social networks in all kinds of situations by the following formula:(14)∑ITGi⟷j=ITGi⟷j+ITGi⟷k⟷j=ITGi⟷j+ITGi⟷k+ITGk⟷j,(15)∑ITGi⟷k=ITGi⟷k+ITGi⟷j+ITGj⟷k.Because there are three possible directional statuses for each edge in Figures2(a) and 2(b), the adjacent edge of node i has three different definitions, which are friends relationship (i⟷j), following relationship (i⟶j), and fan relationship (i⟵j). At the same time, the opposite edge i⟷k of node i also has three definitions. Furthermore, the edge j⟷k has three types of relationships, in which node j and node k are friends, node j follows node k, and node k follows node j. We can use 0, 1, and 2 to stand for the relationships and substitute the three different definitions, and we obtain the following 27 arrangements in Table 1 [30].Table 1
Permutation and combination of 27 conditions.
000001002010011012020021022100101102110111112120121122200201202210211212220221222In the above 27 arrangement cases, because nodei is the source node, we can find some symmetry results, and finally, we can get 15 independent results. And the ITG-based directed node centrality value from information transfer gain clustering coefficient (ITGC) of node i in a directed network can be finally summed by the 15 different independent results in formula (16) as follows:(16)ITGCi=∑t=115ITGi_trianglet×Numbert∑t′=16ITGi_triplet′×Numbert′.ITGCi is the ITG value of node i in a directed network. ∑t=115ITGi_trianglet×Numbert is the weighted number of triangles which use node i as the top vertex (i.e., the information transfer source node), and its weight is the ITG (information transfer gain) contribution ITGi_trianglet from the 15 different types of weighted triangles multiplied by its counted number Numbert. ∑t′=16ITGi_triplet′×Numbert′ is the weighted number of the triples using node i as the top vertex; its weight is the weighted sum of the six ITGi_triplet′ values of different types of triples multiplied by its counted number Numbert′. Similar to undirected clustering coefficients, ITGC has the same characteristic, measuring the tightness of the graph to form tight communities.


## 4. Experiments on Network Robustness Assessment

### 4.1. Simulation of Node Failure Generation Method

Basing on the importance and connectivity of different nodes in the network, there are eight node attack strategies [8] always chosen by researchers to evaluate network robustness such as follows:(1)
The ID removal strategy: the attack starting from the node with the highest degree and node attack strategy uses the initial node degree distribution.(2)
The IB removal strategy: the attack starting from the node with the highest betweenness and node attack strategy uses the initial node betweenness distribution.(3)
TheITG removal strategy: the attack starting from the node with the highest ITG centrality and node attack strategy uses the initial node ITG centrality distribution.(4)
TheIMP removal strategy: the attack starting from the node with the highest IMpv centrality and node attack strategy uses the initial node IMpv centrality distribution.(5)
The RD removal strategy: using the recalculated node degree distribution at every removal step.(6)
The RB removal strategy: using the recalculated node betweenness at every step.(7)
The RTG removal strategy: using the recalculated nodeITG centrality distribution at every removal step.(8)
The RIMP removal strategy: using the recalculated nodeIMpv centrality distribution at every removal step.


### 4.2. Experiment Result

Selection of typical and persuasive dataset is very important to experiment results, and we selected some classical undirected network and directed network dataset including synthetic signed network and real-life large networks used by Albert et al. [13] and Holme et al. [8]. And these typical datasets can be used to validate the network robustness and node vulnerability assessment in undirected and directed networks.From Figures3 to 21, all the prominence in experiment result which was created by ITG, RTG, IMP, and RIMP strategies have be pointed out by red ellipses and text tag. Based on these marks, we can easily find the more strong effects by our proposed ITG and IMpv centralities.Figure 3
l−1&S result of BACSF.Figure 4
CG=V,E result of BACSF.Figure 5
l−1&S result of CallCommunity.Figure 6
CG=V,E result of CallCommunity.Figure 7
l−1&S result of LFR.Figure 8
CG=V,E result of LFR.Figure 9
l−1&S result of OSLOM.Figure 10
CG=V,E result of OSLOM.Figure 11
l−1&S result of subject reference.Figure 12
CG=V,E result of subject reference.Figure 13
l−1&S result of SinaBlog Tweet.Figure 14
CG=V,E result of SinaBlog Tweet.Figure 15
l−1&S result of Calling Record.Figure 16
CG=V,E result of Calling Record.Figure 17
l−1&S result of DBLP.Figure 18
l−1$CG=V,E result of ENRON.Figure 19
l−1&CG=V,E result of Facebook.Figure 20
l−1&CG=V,E result of Facebook (X-axis logarithmic coordinate).Figure 21
l−1 comparison result of iteration times.


#### 4.2.1. Undirected Dataset and Experiment Results

In Table2, the network dataset includes the classical BA scale-free network (a) proposed by Albert et al. [13] (generation parameter is m0=5, m=4, pt=0.8, and n=490) and the undirected call community [31] graph (b) from cellphone calling records in one month in China of a southern city, the LFR (Lancichinetti Fortunato Radicchi) [32] benchmark network with generation parameter of N=1000, kdegree=2, Cmin=20, Cmax=100, u=0.3, and Cdegree=1. For the reason that the LFR benchmark has presented a much solid testing dataset for algorithms and having good performance from other dataset, we used LFR benchmark to generate testing dataset having typical attributes compared with real networks, such as real node degree distribution and heterogeneous distribution of community size. Because the above networks are important undirected networks, the three network datasets are chosen for our research.Table 2
Undirected network dataset.
BACSFaCall CommunitybLFRcNumber of nodeN4902841000Number of linkL1892303015384Edge densityL/N3.861210.669015.3840N: number of nodes; Kdegree: degree power-law distribution index; Cmin: minimum number of nodes; Cmax: maximum number of nodes; u: mix hybrid parameter; Cdegree: community size power-law distribution index.Now we will give the brief introduction of vertical and horizontal coordinates of the graph, in which thex-axis in Figures 3 to 8 stands for the removed node ration (Nrm: the number of removed nodes) to initial graph. The y-axis stands for the relative value of S and l−1 (the ration of S and l−1 after every step of node removal to initial S and l−1 in the network). Figures 7 and 11 consist of 400 calculated results each in 200 networks generated by the four simulated node generation mechanisms above to avoid random deviation (every mechanism generated 50 fault nodes).In calculation ofITG-based node coefficient in undirected networks, all the information transfer gain probability a between nodes i and j for undirected edges will be equal to 0.5 and we would calculate ITG node centrality coefficient of each node and the whole graph.


#### 4.2.2. Experiment Results Analysis for Undirected Dataset

After processing and analyzing the experimental data above, it can be clearly found in Figures3, 5, and 7 that the influence to l−1 is as follows:(1)
When the number of removed nodes is very small that is to say when0.0<Nrm/N<0.005, it is the very early stage of collapse time by node removal of the six different removal strategies and the l−1 curve falls quickly to make the whole graph shrink with a high speed.(2)
During the fall process ofl−1, the RTG curve, RB curve, and RD curve look like falling faster than other three removal strategies.(3)
Among the six different curves ofS, the curves of ITG, IB, and ID are more likely a linear curve than other ones, and the experimental result has shown the correctness of ITG in its almost linear curve with IB and ID.In the common circumstances, the network will be more denser while having the larger value. But in generally, the value of network average cluster coefficient having a sudden increase after the continuous decreasing trend would tell that the node removal can make the network suddenly into disconnected subnetworks. Besides that, Albert et al. [13] and other researchers have also found that when the node having a very high betweenness value leaves the network, it may trigger the huge collapse in the whole network on the system level with a sudden unpredicted speed. Figures 4, 6, and 8 demonstrate the corresponding variation trend of CG=V,E:(1)
It can be also clearly found in Figures4, 6, and 8 that, among the six curves of S, the RTG, ITG, RB, and IB removal strategies are more harmful than RD and ID where in some datasets, the RTG removal strategy is much more harmful than others such as in S and CG=V,E curve of LFR in Figures 7 and 8.(2)
There have been much more rises inITG and IB curves than other curves for the reason that it can break the whole network into disconnected subnetworks with much higher numbers. It has also proved that our ITG node centrality is a very good node centrality by the performance of curve S, CG=V,E, and l−1.


#### 4.2.3. Directed Dataset and Experiment Results

Most social networks are directed networks with directed edges such as e-mail networks, twitter network, and calling record. We selected some representative social network dataset in Table3. The OSLOM (a) dataset was provided by the open source algorithm OSLOM [33] as an example dataset of directed social networks. The subject reference (b) dataset was provided by the INFOMAP algorithm [34] which was a subject reference network from the research of Physics, Chemistry, Biology, and Ecology in 6,128 journals connected by 6,434,916 citations. The SinaBlog Tweet (c) dataset came from the tweeting message reposting chain of one famous Chinese scholar in SinaBlog. The Calling Record (d) dataset was provided by cellphone calling records from another city in one month in China. All the above datasets are typical directed social networks.Table 3
Directed network dataset.
OSLOMaSubjectReferencebSinaBlogTweetcCallingRecorddNumber of nodeN301401492286Number of linkL623430614903934Edge DensityL/N20.71107.65000.998713.7552Thex-axis in Figures 9 to 16 stands for Nrm. The y-axis stands for the relative value of S and l−1. Specially, all the network datasets in Table 3 would be processed as undirected graph in calculation of node betweenness and degree for IB, RB, ID, and RD strategy besides ITG and IMpv strategy. But, all the network datasets in Table 3 would be processed as directed graph in calculation of ITG node centrality coefficient. For the reason that there are only 40 nodes in subject reference (b) dataset, we only calculated the top five nodes.(1) Experiment Resultsof ITG withIMpvto IB, RB, ID, and RD.(2) Experiment Results Analysis for Directed Dataset of ITG withIMpvto IB, RB, ID, and RD. Figures 9 to 16 display the experiment results on directed social network, and we can find that the ITG, IMP, RTG, and RIMP strategies have amplified their harm in directed networks:(1)
l−1 and S: ITG, IMP, RTG, and RIMP are most harmful strategies, and the RIMP strategy is more powerful than RTG especially in the late stage of Figures 11, 13, and 15.(2)
CG=V,E: among the six CG=V,E curves, the sudden rises caused by IMP, ITG, and IB are much more than the rises caused by other strategies where IMP is the most, where in Figure 14, we used the Y-axis logarithmic to show details more clear. The influence to CG=V,E approximately has shown that RIMP > IMP > ITG> RTG > IB > RB > ID > RD.(3)
Especially in the sparse directed network of subject reference,IMDPL−1, ITGL−1, RTGl−1, and RTG CC curves in Figures 11 and 12 finally reached the finest experiment result and caused the biggest cascade. In Figures 13 and 14 of the SinaBlog Tweet network, the RIMPL−1, RIMP CC, RTGl−1, RTGS, and RTG CC curves are the best result of experiment to other curves. In dense network of Calling Record, the RIMPS, RIMP CC, RTGS, and RTG CC also showed the power of IMpv and ITG node centrality by the leading experiment values.Then, we can summarize from Figures3 to 16 that the IMpv- and ITG-based strategies have good experiment result in undirected and directed networks, and it has been proved for its correctness.(3) Directed Experiment Dataset of ITG toIMpv. In this part, we added two typical directed networks with much nodes inside which can be found in Table 4. The first one is the DBLP directed network dataset which is a famous directed heterogeneous information network that contains a dataset of author-centric English literature in the field of computer science with 14736 papers and 14475 authors [28]. We selected the data related to the field of computer, including database, data mining, artificial intelligence, and information retrieval including titles of papers published in various fields, authors who published more than five papers, abstracts of papers, and conferences titles. The another directed network dataset is the well-known ENRON e-mail network among employees of ENRON company from May 11, 1999, to May 21, 2002 (http://www.cs.cmu.edu/∼/enron/). This ENRON e-mail network is divided into small parts by time stamp in each seven days, and the whole network is composed by 150 persons and 1526 emails among them [35, 36]. Its network structure clearly shows some important moments in the company’s development, such as the company’s collapse and the suicide of its former CEO. Dataset C is a Facebook dataset which was collected from survey participants using Facebook app. The dataset includes node features (profiles), circles, and ego networks [37]. The Facebook dataset has been anonymously processed by replacing the Facebook-internal ids for each user with a new value.Table 4
Another directed network dataset.
DBLPaENRONbFacebookcNumber of nodeN143761504039Number of linkL14475152688234Edge DensityL/N1.006910.173321.8455(4) Experiment Results for Directed Dataset of ITG toIMpv.Figures17 and 18 display the experiment results of l−1 and coefficient on directed social network DBLP and ENRON. For the reason of the small scale of ENRON network dataset and very little change in when deleting the top 50 nodes, we only offered the l−1 and coefficient result of it.It is obviously that, in these directed networks, the influence ofIB, ITG, and IMpv has demonstrated a different varying trend in the undirected networks from Table 1. The computation of average inverse geodesic length l always cause high computing costs, while it costs us about 2.4 billion times shortest path search in the dataset of Facebook which has 4039 nodes and 88234 edges (4000∗4000∗3∗50=2.4∗109) and its computation result only can make up the three curves of IBl−1, ITGl−1, and IMPl−1.Figures19 and 20 demonstrate the experiment results of l−1 and coefficient on directed social network Facebook. In order to demonstrate more details, the x-axis in Figure 20 used the logarithmic coordinates.Figure21 demonstrates the comparison result of iteration times in different datasets of Table 4 when computing the directed path-based node importance centrality IMpv. By calculating formula ⟹k>logε−loga/logλ2 (13b), we attain the varying curve of iteration times k to the marginal difference ε, while ε can be calculated by ε≥yk+1−yk. Furthermore, each largest eigenvalue value λ1 and second largest eigenvalue value λ2 of dataset DBLP, ENRON, and Facebook also can be computed.(5) Experiment Results Analysis for Directed Dataset of ITG toIMpv. Figures 16 to 21 display the compared experiment results of IB, ITG, and IMpv node removal strategies on directed social networks. In addition, we explore the varying trend of iteration times k to the marginal difference ε.(1)
Generally after analyzing the demonstrated data in Figures17 and 18, we can find that the influence of node with high ITG values have the most harmful effect to the l−1 in directed networks with low edge density such as DBLP. But in directed networks with high edge density such as ENRON, IB strategy and ITG strategy are just like doing the same effect.(2)
But in the directed network Facebook with a more higher edge density, we can find that theITG node removal strategy suddenly lost its magic and the IMpv removal strategy does the best harmful effect to the Facebook network, while the IB removal strategy followed. And it maybe needs to be varied in more densely connected directed social networks such as Twitter and WeChat.(3)
In Figure21, we can clearly find that the relationship of k and ε. The more densely connected directed network Facebook has the larger iteration times number k. And in dataset Facebook, when ε is more close to zero, iteration times rises to around twenty which has shown high efficiency of our node IMpv computing algorithm.


## 4.1. Simulation of Node Failure Generation Method

Basing on the importance and connectivity of different nodes in the network, there are eight node attack strategies [8] always chosen by researchers to evaluate network robustness such as follows:(1)
The ID removal strategy: the attack starting from the node with the highest degree and node attack strategy uses the initial node degree distribution.(2)
The IB removal strategy: the attack starting from the node with the highest betweenness and node attack strategy uses the initial node betweenness distribution.(3)
TheITG removal strategy: the attack starting from the node with the highest ITG centrality and node attack strategy uses the initial node ITG centrality distribution.(4)
TheIMP removal strategy: the attack starting from the node with the highest IMpv centrality and node attack strategy uses the initial node IMpv centrality distribution.(5)
The RD removal strategy: using the recalculated node degree distribution at every removal step.(6)
The RB removal strategy: using the recalculated node betweenness at every step.(7)
The RTG removal strategy: using the recalculated nodeITG centrality distribution at every removal step.(8)
The RIMP removal strategy: using the recalculated nodeIMpv centrality distribution at every removal step.


## 4.2. Experiment Result

Selection of typical and persuasive dataset is very important to experiment results, and we selected some classical undirected network and directed network dataset including synthetic signed network and real-life large networks used by Albert et al. [13] and Holme et al. [8]. And these typical datasets can be used to validate the network robustness and node vulnerability assessment in undirected and directed networks.From Figures3 to 21, all the prominence in experiment result which was created by ITG, RTG, IMP, and RIMP strategies have be pointed out by red ellipses and text tag. Based on these marks, we can easily find the more strong effects by our proposed ITG and IMpv centralities.Figure 3
l−1&S result of BACSF.Figure 4
CG=V,E result of BACSF.Figure 5
l−1&S result of CallCommunity.Figure 6
CG=V,E result of CallCommunity.Figure 7
l−1&S result of LFR.Figure 8
CG=V,E result of LFR.Figure 9
l−1&S result of OSLOM.Figure 10
CG=V,E result of OSLOM.Figure 11
l−1&S result of subject reference.Figure 12
CG=V,E result of subject reference.Figure 13
l−1&S result of SinaBlog Tweet.Figure 14
CG=V,E result of SinaBlog Tweet.Figure 15
l−1&S result of Calling Record.Figure 16
CG=V,E result of Calling Record.Figure 17
l−1&S result of DBLP.Figure 18
l−1$CG=V,E result of ENRON.Figure 19
l−1&CG=V,E result of Facebook.Figure 20
l−1&CG=V,E result of Facebook (X-axis logarithmic coordinate).Figure 21
l−1 comparison result of iteration times.


### 4.2.1. Undirected Dataset and Experiment Results

In Table2, the network dataset includes the classical BA scale-free network (a) proposed by Albert et al. [13] (generation parameter is m0=5, m=4, pt=0.8, and n=490) and the undirected call community [31] graph (b) from cellphone calling records in one month in China of a southern city, the LFR (Lancichinetti Fortunato Radicchi) [32] benchmark network with generation parameter of N=1000, kdegree=2, Cmin=20, Cmax=100, u=0.3, and Cdegree=1. For the reason that the LFR benchmark has presented a much solid testing dataset for algorithms and having good performance from other dataset, we used LFR benchmark to generate testing dataset having typical attributes compared with real networks, such as real node degree distribution and heterogeneous distribution of community size. Because the above networks are important undirected networks, the three network datasets are chosen for our research.Table 2
Undirected network dataset.
BACSFaCall CommunitybLFRcNumber of nodeN4902841000Number of linkL1892303015384Edge densityL/N3.861210.669015.3840N: number of nodes; Kdegree: degree power-law distribution index; Cmin: minimum number of nodes; Cmax: maximum number of nodes; u: mix hybrid parameter; Cdegree: community size power-law distribution index.Now we will give the brief introduction of vertical and horizontal coordinates of the graph, in which thex-axis in Figures 3 to 8 stands for the removed node ration (Nrm: the number of removed nodes) to initial graph. The y-axis stands for the relative value of S and l−1 (the ration of S and l−1 after every step of node removal to initial S and l−1 in the network). Figures 7 and 11 consist of 400 calculated results each in 200 networks generated by the four simulated node generation mechanisms above to avoid random deviation (every mechanism generated 50 fault nodes).In calculation ofITG-based node coefficient in undirected networks, all the information transfer gain probability a between nodes i and j for undirected edges will be equal to 0.5 and we would calculate ITG node centrality coefficient of each node and the whole graph.


### 4.2.2. Experiment Results Analysis for Undirected Dataset

After processing and analyzing the experimental data above, it can be clearly found in Figures3, 5, and 7 that the influence to l−1 is as follows:(1)
When the number of removed nodes is very small that is to say when0.0<Nrm/N<0.005, it is the very early stage of collapse time by node removal of the six different removal strategies and the l−1 curve falls quickly to make the whole graph shrink with a high speed.(2)
During the fall process ofl−1, the RTG curve, RB curve, and RD curve look like falling faster than other three removal strategies.(3)
Among the six different curves ofS, the curves of ITG, IB, and ID are more likely a linear curve than other ones, and the experimental result has shown the correctness of ITG in its almost linear curve with IB and ID.In the common circumstances, the network will be more denser while having the larger value. But in generally, the value of network average cluster coefficient having a sudden increase after the continuous decreasing trend would tell that the node removal can make the network suddenly into disconnected subnetworks. Besides that, Albert et al. [13] and other researchers have also found that when the node having a very high betweenness value leaves the network, it may trigger the huge collapse in the whole network on the system level with a sudden unpredicted speed. Figures 4, 6, and 8 demonstrate the corresponding variation trend of CG=V,E:(1)
It can be also clearly found in Figures4, 6, and 8 that, among the six curves of S, the RTG, ITG, RB, and IB removal strategies are more harmful than RD and ID where in some datasets, the RTG removal strategy is much more harmful than others such as in S and CG=V,E curve of LFR in Figures 7 and 8.(2)
There have been much more rises inITG and IB curves than other curves for the reason that it can break the whole network into disconnected subnetworks with much higher numbers. It has also proved that our ITG node centrality is a very good node centrality by the performance of curve S, CG=V,E, and l−1.


### 4.2.3. Directed Dataset and Experiment Results

Most social networks are directed networks with directed edges such as e-mail networks, twitter network, and calling record. We selected some representative social network dataset in Table3. The OSLOM (a) dataset was provided by the open source algorithm OSLOM [33] as an example dataset of directed social networks. The subject reference (b) dataset was provided by the INFOMAP algorithm [34] which was a subject reference network from the research of Physics, Chemistry, Biology, and Ecology in 6,128 journals connected by 6,434,916 citations. The SinaBlog Tweet (c) dataset came from the tweeting message reposting chain of one famous Chinese scholar in SinaBlog. The Calling Record (d) dataset was provided by cellphone calling records from another city in one month in China. All the above datasets are typical directed social networks.Table 3
Directed network dataset.
OSLOMaSubjectReferencebSinaBlogTweetcCallingRecorddNumber of nodeN301401492286Number of linkL623430614903934Edge DensityL/N20.71107.65000.998713.7552Thex-axis in Figures 9 to 16 stands for Nrm. The y-axis stands for the relative value of S and l−1. Specially, all the network datasets in Table 3 would be processed as undirected graph in calculation of node betweenness and degree for IB, RB, ID, and RD strategy besides ITG and IMpv strategy. But, all the network datasets in Table 3 would be processed as directed graph in calculation of ITG node centrality coefficient. For the reason that there are only 40 nodes in subject reference (b) dataset, we only calculated the top five nodes.(1) Experiment Resultsof ITG withIMpvto IB, RB, ID, and RD.(2) Experiment Results Analysis for Directed Dataset of ITG withIMpvto IB, RB, ID, and RD. Figures 9 to 16 display the experiment results on directed social network, and we can find that the ITG, IMP, RTG, and RIMP strategies have amplified their harm in directed networks:(1)
l−1 and S: ITG, IMP, RTG, and RIMP are most harmful strategies, and the RIMP strategy is more powerful than RTG especially in the late stage of Figures 11, 13, and 15.(2)
CG=V,E: among the six CG=V,E curves, the sudden rises caused by IMP, ITG, and IB are much more than the rises caused by other strategies where IMP is the most, where in Figure 14, we used the Y-axis logarithmic to show details more clear. The influence to CG=V,E approximately has shown that RIMP > IMP > ITG> RTG > IB > RB > ID > RD.(3)
Especially in the sparse directed network of subject reference,IMDPL−1, ITGL−1, RTGl−1, and RTG CC curves in Figures 11 and 12 finally reached the finest experiment result and caused the biggest cascade. In Figures 13 and 14 of the SinaBlog Tweet network, the RIMPL−1, RIMP CC, RTGl−1, RTGS, and RTG CC curves are the best result of experiment to other curves. In dense network of Calling Record, the RIMPS, RIMP CC, RTGS, and RTG CC also showed the power of IMpv and ITG node centrality by the leading experiment values.Then, we can summarize from Figures3 to 16 that the IMpv- and ITG-based strategies have good experiment result in undirected and directed networks, and it has been proved for its correctness.(3) Directed Experiment Dataset of ITG toIMpv. In this part, we added two typical directed networks with much nodes inside which can be found in Table 4. The first one is the DBLP directed network dataset which is a famous directed heterogeneous information network that contains a dataset of author-centric English literature in the field of computer science with 14736 papers and 14475 authors [28]. We selected the data related to the field of computer, including database, data mining, artificial intelligence, and information retrieval including titles of papers published in various fields, authors who published more than five papers, abstracts of papers, and conferences titles. The another directed network dataset is the well-known ENRON e-mail network among employees of ENRON company from May 11, 1999, to May 21, 2002 (http://www.cs.cmu.edu/∼/enron/). This ENRON e-mail network is divided into small parts by time stamp in each seven days, and the whole network is composed by 150 persons and 1526 emails among them [35, 36]. Its network structure clearly shows some important moments in the company’s development, such as the company’s collapse and the suicide of its former CEO. Dataset C is a Facebook dataset which was collected from survey participants using Facebook app. The dataset includes node features (profiles), circles, and ego networks [37]. The Facebook dataset has been anonymously processed by replacing the Facebook-internal ids for each user with a new value.Table 4
Another directed network dataset.
DBLPaENRONbFacebookcNumber of nodeN143761504039Number of linkL14475152688234Edge DensityL/N1.006910.173321.8455(4) Experiment Results for Directed Dataset of ITG toIMpv.Figures17 and 18 display the experiment results of l−1 and coefficient on directed social network DBLP and ENRON. For the reason of the small scale of ENRON network dataset and very little change in when deleting the top 50 nodes, we only offered the l−1 and coefficient result of it.It is obviously that, in these directed networks, the influence ofIB, ITG, and IMpv has demonstrated a different varying trend in the undirected networks from Table 1. The computation of average inverse geodesic length l always cause high computing costs, while it costs us about 2.4 billion times shortest path search in the dataset of Facebook which has 4039 nodes and 88234 edges (4000∗4000∗3∗50=2.4∗109) and its computation result only can make up the three curves of IBl−1, ITGl−1, and IMPl−1.Figures19 and 20 demonstrate the experiment results of l−1 and coefficient on directed social network Facebook. In order to demonstrate more details, the x-axis in Figure 20 used the logarithmic coordinates.Figure21 demonstrates the comparison result of iteration times in different datasets of Table 4 when computing the directed path-based node importance centrality IMpv. By calculating formula ⟹k>logε−loga/logλ2 (13b), we attain the varying curve of iteration times k to the marginal difference ε, while ε can be calculated by ε≥yk+1−yk. Furthermore, each largest eigenvalue value λ1 and second largest eigenvalue value λ2 of dataset DBLP, ENRON, and Facebook also can be computed.(5) Experiment Results Analysis for Directed Dataset of ITG toIMpv. Figures 16 to 21 display the compared experiment results of IB, ITG, and IMpv node removal strategies on directed social networks. In addition, we explore the varying trend of iteration times k to the marginal difference ε.(1)
Generally after analyzing the demonstrated data in Figures17 and 18, we can find that the influence of node with high ITG values have the most harmful effect to the l−1 in directed networks with low edge density such as DBLP. But in directed networks with high edge density such as ENRON, IB strategy and ITG strategy are just like doing the same effect.(2)
But in the directed network Facebook with a more higher edge density, we can find that theITG node removal strategy suddenly lost its magic and the IMpv removal strategy does the best harmful effect to the Facebook network, while the IB removal strategy followed. And it maybe needs to be varied in more densely connected directed social networks such as Twitter and WeChat.(3)
In Figure21, we can clearly find that the relationship of k and ε. The more densely connected directed network Facebook has the larger iteration times number k. And in dataset Facebook, when ε is more close to zero, iteration times rises to around twenty which has shown high efficiency of our node IMpv computing algorithm.


## 4.2.1. Undirected Dataset and Experiment Results

In Table2, the network dataset includes the classical BA scale-free network (a) proposed by Albert et al. [13] (generation parameter is m0=5, m=4, pt=0.8, and n=490) and the undirected call community [31] graph (b) from cellphone calling records in one month in China of a southern city, the LFR (Lancichinetti Fortunato Radicchi) [32] benchmark network with generation parameter of N=1000, kdegree=2, Cmin=20, Cmax=100, u=0.3, and Cdegree=1. For the reason that the LFR benchmark has presented a much solid testing dataset for algorithms and having good performance from other dataset, we used LFR benchmark to generate testing dataset having typical attributes compared with real networks, such as real node degree distribution and heterogeneous distribution of community size. Because the above networks are important undirected networks, the three network datasets are chosen for our research.Table 2
Undirected network dataset.
BACSFaCall CommunitybLFRcNumber of nodeN4902841000Number of linkL1892303015384Edge densityL/N3.861210.669015.3840N: number of nodes; Kdegree: degree power-law distribution index; Cmin: minimum number of nodes; Cmax: maximum number of nodes; u: mix hybrid parameter; Cdegree: community size power-law distribution index.Now we will give the brief introduction of vertical and horizontal coordinates of the graph, in which thex-axis in Figures 3 to 8 stands for the removed node ration (Nrm: the number of removed nodes) to initial graph. The y-axis stands for the relative value of S and l−1 (the ration of S and l−1 after every step of node removal to initial S and l−1 in the network). Figures 7 and 11 consist of 400 calculated results each in 200 networks generated by the four simulated node generation mechanisms above to avoid random deviation (every mechanism generated 50 fault nodes).In calculation ofITG-based node coefficient in undirected networks, all the information transfer gain probability a between nodes i and j for undirected edges will be equal to 0.5 and we would calculate ITG node centrality coefficient of each node and the whole graph.


## 4.2.2. Experiment Results Analysis for Undirected Dataset

After processing and analyzing the experimental data above, it can be clearly found in Figures3, 5, and 7 that the influence to l−1 is as follows:(1)
When the number of removed nodes is very small that is to say when0.0<Nrm/N<0.005, it is the very early stage of collapse time by node removal of the six different removal strategies and the l−1 curve falls quickly to make the whole graph shrink with a high speed.(2)
During the fall process ofl−1, the RTG curve, RB curve, and RD curve look like falling faster than other three removal strategies.(3)
Among the six different curves ofS, the curves of ITG, IB, and ID are more likely a linear curve than other ones, and the experimental result has shown the correctness of ITG in its almost linear curve with IB and ID.In the common circumstances, the network will be more denser while having the larger value. But in generally, the value of network average cluster coefficient having a sudden increase after the continuous decreasing trend would tell that the node removal can make the network suddenly into disconnected subnetworks. Besides that, Albert et al. [13] and other researchers have also found that when the node having a very high betweenness value leaves the network, it may trigger the huge collapse in the whole network on the system level with a sudden unpredicted speed. Figures 4, 6, and 8 demonstrate the corresponding variation trend of CG=V,E:(1)
It can be also clearly found in Figures4, 6, and 8 that, among the six curves of S, the RTG, ITG, RB, and IB removal strategies are more harmful than RD and ID where in some datasets, the RTG removal strategy is much more harmful than others such as in S and CG=V,E curve of LFR in Figures 7 and 8.(2)
There have been much more rises inITG and IB curves than other curves for the reason that it can break the whole network into disconnected subnetworks with much higher numbers. It has also proved that our ITG node centrality is a very good node centrality by the performance of curve S, CG=V,E, and l−1.


## 4.2.3. Directed Dataset and Experiment Results

Most social networks are directed networks with directed edges such as e-mail networks, twitter network, and calling record. We selected some representative social network dataset in Table3. The OSLOM (a) dataset was provided by the open source algorithm OSLOM [33] as an example dataset of directed social networks. The subject reference (b) dataset was provided by the INFOMAP algorithm [34] which was a subject reference network from the research of Physics, Chemistry, Biology, and Ecology in 6,128 journals connected by 6,434,916 citations. The SinaBlog Tweet (c) dataset came from the tweeting message reposting chain of one famous Chinese scholar in SinaBlog. The Calling Record (d) dataset was provided by cellphone calling records from another city in one month in China. All the above datasets are typical directed social networks.Table 3
Directed network dataset.
OSLOMaSubjectReferencebSinaBlogTweetcCallingRecorddNumber of nodeN301401492286Number of linkL623430614903934Edge DensityL/N20.71107.65000.998713.7552Thex-axis in Figures 9 to 16 stands for Nrm. The y-axis stands for the relative value of S and l−1. Specially, all the network datasets in Table 3 would be processed as undirected graph in calculation of node betweenness and degree for IB, RB, ID, and RD strategy besides ITG and IMpv strategy. But, all the network datasets in Table 3 would be processed as directed graph in calculation of ITG node centrality coefficient. For the reason that there are only 40 nodes in subject reference (b) dataset, we only calculated the top five nodes.(1) Experiment Resultsof ITG withIMpvto IB, RB, ID, and RD.(2) Experiment Results Analysis for Directed Dataset of ITG withIMpvto IB, RB, ID, and RD. Figures 9 to 16 display the experiment results on directed social network, and we can find that the ITG, IMP, RTG, and RIMP strategies have amplified their harm in directed networks:(1)
l−1 and S: ITG, IMP, RTG, and RIMP are most harmful strategies, and the RIMP strategy is more powerful than RTG especially in the late stage of Figures 11, 13, and 15.(2)
CG=V,E: among the six CG=V,E curves, the sudden rises caused by IMP, ITG, and IB are much more than the rises caused by other strategies where IMP is the most, where in Figure 14, we used the Y-axis logarithmic to show details more clear. The influence to CG=V,E approximately has shown that RIMP > IMP > ITG> RTG > IB > RB > ID > RD.(3)
Especially in the sparse directed network of subject reference,IMDPL−1, ITGL−1, RTGl−1, and RTG CC curves in Figures 11 and 12 finally reached the finest experiment result and caused the biggest cascade. In Figures 13 and 14 of the SinaBlog Tweet network, the RIMPL−1, RIMP CC, RTGl−1, RTGS, and RTG CC curves are the best result of experiment to other curves. In dense network of Calling Record, the RIMPS, RIMP CC, RTGS, and RTG CC also showed the power of IMpv and ITG node centrality by the leading experiment values.Then, we can summarize from Figures3 to 16 that the IMpv- and ITG-based strategies have good experiment result in undirected and directed networks, and it has been proved for its correctness.(3) Directed Experiment Dataset of ITG toIMpv. In this part, we added two typical directed networks with much nodes inside which can be found in Table 4. The first one is the DBLP directed network dataset which is a famous directed heterogeneous information network that contains a dataset of author-centric English literature in the field of computer science with 14736 papers and 14475 authors [28]. We selected the data related to the field of computer, including database, data mining, artificial intelligence, and information retrieval including titles of papers published in various fields, authors who published more than five papers, abstracts of papers, and conferences titles. The another directed network dataset is the well-known ENRON e-mail network among employees of ENRON company from May 11, 1999, to May 21, 2002 (http://www.cs.cmu.edu/∼/enron/). This ENRON e-mail network is divided into small parts by time stamp in each seven days, and the whole network is composed by 150 persons and 1526 emails among them [35, 36]. Its network structure clearly shows some important moments in the company’s development, such as the company’s collapse and the suicide of its former CEO. Dataset C is a Facebook dataset which was collected from survey participants using Facebook app. The dataset includes node features (profiles), circles, and ego networks [37]. The Facebook dataset has been anonymously processed by replacing the Facebook-internal ids for each user with a new value.Table 4
Another directed network dataset.
DBLPaENRONbFacebookcNumber of nodeN143761504039Number of linkL14475152688234Edge DensityL/N1.006910.173321.8455(4) Experiment Results for Directed Dataset of ITG toIMpv.Figures17 and 18 display the experiment results of l−1 and coefficient on directed social network DBLP and ENRON. For the reason of the small scale of ENRON network dataset and very little change in when deleting the top 50 nodes, we only offered the l−1 and coefficient result of it.It is obviously that, in these directed networks, the influence ofIB, ITG, and IMpv has demonstrated a different varying trend in the undirected networks from Table 1. The computation of average inverse geodesic length l always cause high computing costs, while it costs us about 2.4 billion times shortest path search in the dataset of Facebook which has 4039 nodes and 88234 edges (4000∗4000∗3∗50=2.4∗109) and its computation result only can make up the three curves of IBl−1, ITGl−1, and IMPl−1.Figures19 and 20 demonstrate the experiment results of l−1 and coefficient on directed social network Facebook. In order to demonstrate more details, the x-axis in Figure 20 used the logarithmic coordinates.Figure21 demonstrates the comparison result of iteration times in different datasets of Table 4 when computing the directed path-based node importance centrality IMpv. By calculating formula ⟹k>logε−loga/logλ2 (13b), we attain the varying curve of iteration times k to the marginal difference ε, while ε can be calculated by ε≥yk+1−yk. Furthermore, each largest eigenvalue value λ1 and second largest eigenvalue value λ2 of dataset DBLP, ENRON, and Facebook also can be computed.(5) Experiment Results Analysis for Directed Dataset of ITG toIMpv. Figures 16 to 21 display the compared experiment results of IB, ITG, and IMpv node removal strategies on directed social networks. In addition, we explore the varying trend of iteration times k to the marginal difference ε.(1)
Generally after analyzing the demonstrated data in Figures17 and 18, we can find that the influence of node with high ITG values have the most harmful effect to the l−1 in directed networks with low edge density such as DBLP. But in directed networks with high edge density such as ENRON, IB strategy and ITG strategy are just like doing the same effect.(2)
But in the directed network Facebook with a more higher edge density, we can find that theITG node removal strategy suddenly lost its magic and the IMpv removal strategy does the best harmful effect to the Facebook network, while the IB removal strategy followed. And it maybe needs to be varied in more densely connected directed social networks such as Twitter and WeChat.(3)
In Figure21, we can clearly find that the relationship of k and ε. The more densely connected directed network Facebook has the larger iteration times number k. And in dataset Facebook, when ε is more close to zero, iteration times rises to around twenty which has shown high efficiency of our node IMpv computing algorithm.


## 5. Conclusion

In this paper, we have proved new information transfer gain- (ITG-) based probability clustering coefficient and directed node importance centrality IMpv for measuring directed graph. Our comparisons in the variation trend of some key performance quantities of network robustness and node vulnerability assessment are useful and helpful. Comparison could help us to capture this cascading effect in directed online social networks. Experiments results showed that node RIMP and RTG strategies are more harmful than node betweenness-based strategies such as RB and IB in directed social networks including real Sina Blogging and Calling Record network. With sufficient experiments in synthetic signed networks and real networks derived from directed online social media and directed human mobile phone calling network, it has been proved that our ITG- and IMpv-based directed social network robustness and node vulnerability assessment method is more accurate, efficient, and faster than several classical traditional centrality methods such as degree and betweenness. Furthermore, we will carry out our ITG centrality on more types and more large-scale directed social networks.In addition, we propose a new proving process of directed node importance centralityIMpv in Section 3.2.4. By rigorous mathematical derivation and approximate calculation, to the best knowledge of us, we attain the varying trend of iteration times k to the marginal difference ε on directed social networks for the first time to our best knowledge.



---

*Source: 8715619-2020-11-21.xml*