# Roles of Clustering Coefficient for the Network Reconstruction

Authors: Jingti Han; Changmei Mao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

It is important to establish relations between the network reconstruction and the topological dynamical structure of networks. In this article, we quantify the effect for two types of network topologies on the performance of network reconstruction. First, we generate two network modes with variable clustering coefficient based on Holme-Kim model and Newman-Watts small-world model, then we reconstruct the artificial networks by using a novel framework calledL1-norm minimization algorithm based on a theory called compressive sensing (CS), a framework for recovering sparse signals. The results of the simulation experiment show that the accuracy rate for the network reconstruction is a monotonically increasing function of the clustering coefficient in Holme-Kim model, whereas the opposite occurs in Newman-Watts small-world network. And this yet demonstrates that the larger the network size, the higher the accuracy rate. Morever, we compare the results of CS with orthogonal matching pursuit (OMP), a greedy algorithm. The results show that the accuracy rate of L1-norm minimization method is 10% higher than that of OMP, and OMP yields 1.2 times the computation speed of L1-norm minimization. Our work demonstrates that the topological structure of network has influence on the accurate reconstruction and it is helpful for offering proper method for the network reconstruction.


---

## Body

## 1. Introduction

Network reconstruction has attracted much attention for various collective dynamical behaviors [1–3]. The concept of complex network reconstruction is proposed for the first time by Guimerà [4]. It is an inverted problem that can rebuild the existing network to yield estimates of the true network properties and plays significant role in various aspects, such as locating the source of disease [5, 6], idenfying hidden information, preventing virus transmission [7, 8], and predicting risk spreading in financial networks.When dealing with the network reconstruction problem, we should think about the reliability of network data since the accessible data may be fragmentary and limited in consideration of network size. Efficient approaches to solve the reconstruction problem with low data requirements are mainly obtained from methods as Link prediction [9], Bayesian reasoning [10], ODE [11], and so on. Recently, a theory called compressive sensing (CS), used for recovering sparse signal [12, 13], such as image reconstruction, large-scale sensor-network data processing, and coupled-oscillator networks reconstruction [14], either with time series (continuous-time) data, which has been outstanding in nonlinear dynamics with interactions among nodes [15], or discrete time series, which remains deeper researching [16], can reconstruct a propagation network using small data set information extracted from experiments or observations [17–19]. L1-norm minimization (Basis Pursuit), which can solve sparse problem, is often used as one kind of algorithm for CS. Under stochastic dynamical process, Shen et al. reconstruct networks from limited time series. Wang et al. [20] uncover interaction networks from small amount of data based on CS. Indeed, such studies proposed a wide range of issues related to accurate network reconstruction for diverse fields. Most of them studied sparse networks in applications from gene-regulatory networks [21], coupled oscillator networks, to social networks [22]. In real world network, human Brain Network has been investigated under CS [23]; in [24] the authors took into account three directed real-world networks, Football, USTop500, andC. elegans, and tested two methods on the reconstruction for the three networks. In [25], CS is exploited for reducing the memory cost in switches and routers. In [26], the authors gather and spread information across a large P2P overlay network efficiently by CS.Prior studies about network reconstruction mainly focused on analyzing the collective dynamics complex networks with evolutionary game data. Santos et al. [27] study the mechanism of cooperative evolution with data from game theory. Rong et al. [28] investigate, in the networked prisoner’s dilemma game, how the degree-mixing schema influences the cooperation. Besides the network games [29, 30], the network synchronization [31], the topological structure [32, 33], and so on are popular research topics in the field of complex system. Specifically, analyzing the dynamic properties of complex system is of great significance. The topological characteristics paly important role on the network controllability [34]. Guo et al. [35] investigate the role of the assortative coeffcicent for the network reconstruction and find that when the assortative coefficient is positive, the L1-norm minimization method could regenerate the social network more accurately. However, whether network topology can affect the reconstruction accuracy and choose proper method is important for network reconstruction. Inspired by this, we investigate the effect on the accuracy rate of the network reconstruction by L1-norm minimization method with different topological structure of networks measured by variable clustering coefficient among two type network models. Newman and Watts raise small-world network, highlighting their high clustering and shortest average path length [36]. Barabási and Albert (BA) established a network with both growth mechanism and preferential attachment mechanism [37, 38]; the nodes’ degree of the system follows the principle of the power-law distribution. The existing classical network model that incorporates both properties is called Holme–Kim model [39]. It is built based on BA model and possesses the scale-free characteristic. In this article, we control the parameter of the model by adjusting the change of the clustering coefficient. To verify the restructing algorithm we have mentioned, we model various network structures with variable clustering coefficient and investigate the relation between accuracy and clustering coefficient. At last, we also investigate the performance by using orthogonal matching pursuit (OMP), a greedy algorithm, which shows difference with L1-norm minimization.In this paper, first we generate a series networks by Holme–Kim model and Newman-Watts small-world model, then we reveal the structure of network with evolutionary-game data by usingL1-norm minimization. Furthermore, we compare our framework with OMP, another method for network reconstruction. The results show that, with the network topological structure changing, our method is 10% higher than that of OMP in terms of success rate (SR), which measures the accuracy of network reconstruction. Specially, Holme–Kim model acts distinctly different among the two algorithms. Meanwhile, OMP has 1.2 times the convergence rate of L1-norm minimization. Our work shows the accuracy of prediction for two types of network topologies, with the two methods performing differently, and choosing the proper method is important.


## 2. Methods

We address the mechanism of uncovering two types network topologies with evolutionary PD game time series data based onL1-norm minimization, one kind of compressive sensing method. It is carried out through exploring two evolutionary games generating in Holme–Kim networks and Newman-Watts small-world networks; individual interactive information is accessible, then we make an attempt to decode the network structure from measurable data.


### 2.1. Reconstruction Processes

CS is first used for finding solutions to underdetermine linear systems through processing signal to acquire and remodeling signal. The advantage of CS [40–42] is that it can reconstruct a small number of linear measurements of the signal that contain enough information. It often happens on the fact that abundant signals are compressible or sparse when they are expressed in the proper basis and frame. The purpose of CS is mainly aimed at reconstructing vector X fromG (X∈RN,G is inear measurements); convex optimization problem can be expressed as follows:(1)minX1s.t.G=Φ·X,from which the vector G∈RM denotes the measurement vector and measurement matrix Φ∈RM×N whose rows have unit length projects data. X1=∑i=1N‍Xi is the L1-norm of vectorX. As a kind of compression estimates, the calculation speed of L1-norm method is slow, the measurement data required is small, and the precision is high. Optimum solution to the convex optimization can be accessible [43]; it has been widely used for network reconstruction problem easily [44]. Considering that the length of an unknown vector is much more than the observable measurements (N≫M) and the number of non-zero elements is less than M, all these are main advantages of CS. The measurement vector G and matrix Φ are generated from the evolutionary game progress where accessible data about strategy and payoff for each agent can be got from the dynamic interaction. In general, two game theories are used to investigate cooperation in social networks; one is prisoner’s dilemma (PD) game [45], and the other is snowdrift game (SG) [46]. Recently, the prisoner’s dilemma (PD) game has been used combined with spatial or topological dimension [47, 48]. PD game has been a framework to exploit cooperation for complex social network among nodes [49]; it can serve for network reconstruction. In fact, the structure of network often can affect the style of cooperation; much research has been done about it. In terms of mechanism for PD game, there exist many ways to deal with cooperation; in [50], it is demonstrated that costly punishment may decrease cooperation sometimes. In general, two strategiesS belong to an agent: cooperation (C) or defection (D), the strategy matrices for cooperation isS(C)=(1,0)T and strategy matrices for defection isS(D)=(0,1)T; for the PD game, we can simplify the payoff matrices as follows: we implement Eq. (1) based on evolutionary game data with numerical computations through complex networks. The payoff matricesP are(2)P=101+b0,where b(0<b<1) is the parameter that can indicate the temptation to defect; each agent plays the PD game with its neighbors and gains payoffs step by step. For example, as for agent i, after one round, the payoff Zi is(3)Zi=∑j∈ΓiSiT·P·Sj,in Eq. (3) Si denotes the strategies of agent i and Sj denotes the strategies of agent j respectively, and Zi is total payoff over all the neighbor set Γi of i. After each round of the game, the agent will adjust its own strategy according to the its payoff and the neighbors’, allowing them to achieve the desired benefits in subsequent rounds, thus forming game evolution process. Common strategy evolution rules have imitated the best Copy dynamics, Fermi dynamics, and so on. The experimental part of this paper will use the Fermi dynamics rule to carry out the PD game evolution. The rule of the dynamics of Fermi: the probability of the node i next round learning node j’s strategy is [51](4)QSi⟵Sj=11+expZi-Zj/κ. The parameter κ denotes the rationality of the player in the game; when it comes close to zero, players will only learn the strategy, the revenue of which is higher than its own in this round. When κ increases, the probability of a player learning a low yield neighbor strategy will increase, which can be expressed by κ being 0 if Zj<Zi and 1 if Zi<Zj. When κ approaches ∝, this means that the player chooses completely random decision making.Each agent possesses one node in the evolutionary game. Assume that the number of nodes in the game network isN; the links between nodes can be represented by an adjacency matrixA with N order. If node j is the neighbor of node i, the matrix element aij=1; otherwise aij=0. The total payoff for node i can be expressed as follows:(5)Git=ai1SiTt·P·S1t+···+ai,i-1SiTt·P·Si-1t+ai,i+1SiTt·P·Si+1t+aiNSiTt·P·SNt, in which aij(j=1,…,i-1,i+1,…,N) denotes connection between agent i and its neighbor j, and aijSiT(t)·P·Sj(t)(j=1,,i-1,i+1,,N) denotes the total payoff of node i from the PD game with j, and t denotes the the total rounds that all agents implement PD game with their own neighbors. And Φi is the payoff matrix for node i, expressed as follows:(6)Φi=Fi1t1Fi,2t1⋯Fint1Fi1t2Fi,2t2⋯Fint2Fi1t3Fi,2t3⋯Fint3⋮⋮⋮⋮Fi1tmFi,2tm⋯Fi,ntm,then we solve the data information(7)Ai=ai1,…,ai,ai-1,ai,i+1,…,aiNT,and(8)Gx=Git1,Git2,⋯GitmT,where Fij(ti)=SiT·P·Sj(ti) and Eq. (6)–(8) satisfy the following equation: (9)Gi=Φi·Ai.In a similar fashion, through compressive sensing method, the remaining agents yield payoff from their neighbor-connection; the overall network adjacency matrix can be expressed asA=(A1,A2,…,An). Due to the sparsity of Ai, it is assured that it can be solved by using CS theory to get accurate results from partial time series data (η≡m/n, where η denotes the length of time series data, and m denotes the number of moment: for example, η=60% means that the number of used measurements equals 0.6N).


### 2.2. Network Model

A network can be denoted as an adjacent matrixW=(aij)N×N, which contains N nodes and E edges. In general, ki represents the degree of node i, and Ci represents the clustering coefficients of node i; it represents the ratio between the number of closed triplets and the total number of connected triplets of vertices; it can be calculated as follows:(10)Ci=1kiki-1∑j,k=1Naijajkaki, where aij=1 denotes that there exists a partnership between node i and j, so when aijajkaki=1, then a triangle forms among nodes i, j, k. The whole network clustering coefficient should be expressed as(11)C=1N∑i=1NCi.We validated our method by using PD games data occurring in Holme–Kim networks. Contrary to BA model, Holme–Kim model adds Triad Formation process (TF process), in order to change the principle when a new node is attached to an existing node by the principle called Preferential Attachment process (PA process). By this way, it not only makes the network growth mode more flexible, but also increases the clustering coefficient. In the Holme–Kim model, the evolution process of network has three driver factors: growth, preference attachment, and triad formation. The algorithm of the Holme–Kim model is shown as follows [52]:Growth. At the beginning, the network has m0 nodes; on each time step, one new node υ with m edges connects with the existing nodes (m⩽m0).Preferential Attachment. There is preference when the new node υ chooses other nodes to connect. The ratio of choosing node i depends on the degree of this node. It can be expressed as follows:(12)Πi=ki∑jkj.Triad Formation. After adding an edge between new node υ and i′s neighbor in the previous PA step, another neighbor node of i is chosen to connect with node υ with probability Pt. The network structure varies as Pt changes; Figure 1 shows the relationship between probabilities Pt and clustering coefficients CH of network. It is obvious that as Pt increases, CH grows as well, which implies that the network gets more closely.Figure 1
Correlation between theCH and Pt in Holme–Kim network.Another PD game data occurring in Newman-Watts small-world network (homogeneous small-world network) exhibits a homogeneous connectivity distribution, in the sense that the number of connections for all nodes is the same; the algorithm steps can be described as(1)
First, initializing a network withN nodes, it is ring-shaped; each node has 2k neighbors, k>0, k is an integer (usually small).(2)
Then adding an edge between the unconnected nodes with probabilityPN (0<PN≪1).Dunring the process, there will be multiple edges between any pair of nodes. All nodes will have no self-loops; the clustering coefficients of the network are denoted asCN.


## 2.1. Reconstruction Processes

CS is first used for finding solutions to underdetermine linear systems through processing signal to acquire and remodeling signal. The advantage of CS [40–42] is that it can reconstruct a small number of linear measurements of the signal that contain enough information. It often happens on the fact that abundant signals are compressible or sparse when they are expressed in the proper basis and frame. The purpose of CS is mainly aimed at reconstructing vector X fromG (X∈RN,G is inear measurements); convex optimization problem can be expressed as follows:(1)minX1s.t.G=Φ·X,from which the vector G∈RM denotes the measurement vector and measurement matrix Φ∈RM×N whose rows have unit length projects data. X1=∑i=1N‍Xi is the L1-norm of vectorX. As a kind of compression estimates, the calculation speed of L1-norm method is slow, the measurement data required is small, and the precision is high. Optimum solution to the convex optimization can be accessible [43]; it has been widely used for network reconstruction problem easily [44]. Considering that the length of an unknown vector is much more than the observable measurements (N≫M) and the number of non-zero elements is less than M, all these are main advantages of CS. The measurement vector G and matrix Φ are generated from the evolutionary game progress where accessible data about strategy and payoff for each agent can be got from the dynamic interaction. In general, two game theories are used to investigate cooperation in social networks; one is prisoner’s dilemma (PD) game [45], and the other is snowdrift game (SG) [46]. Recently, the prisoner’s dilemma (PD) game has been used combined with spatial or topological dimension [47, 48]. PD game has been a framework to exploit cooperation for complex social network among nodes [49]; it can serve for network reconstruction. In fact, the structure of network often can affect the style of cooperation; much research has been done about it. In terms of mechanism for PD game, there exist many ways to deal with cooperation; in [50], it is demonstrated that costly punishment may decrease cooperation sometimes. In general, two strategiesS belong to an agent: cooperation (C) or defection (D), the strategy matrices for cooperation isS(C)=(1,0)T and strategy matrices for defection isS(D)=(0,1)T; for the PD game, we can simplify the payoff matrices as follows: we implement Eq. (1) based on evolutionary game data with numerical computations through complex networks. The payoff matricesP are(2)P=101+b0,where b(0<b<1) is the parameter that can indicate the temptation to defect; each agent plays the PD game with its neighbors and gains payoffs step by step. For example, as for agent i, after one round, the payoff Zi is(3)Zi=∑j∈ΓiSiT·P·Sj,in Eq. (3) Si denotes the strategies of agent i and Sj denotes the strategies of agent j respectively, and Zi is total payoff over all the neighbor set Γi of i. After each round of the game, the agent will adjust its own strategy according to the its payoff and the neighbors’, allowing them to achieve the desired benefits in subsequent rounds, thus forming game evolution process. Common strategy evolution rules have imitated the best Copy dynamics, Fermi dynamics, and so on. The experimental part of this paper will use the Fermi dynamics rule to carry out the PD game evolution. The rule of the dynamics of Fermi: the probability of the node i next round learning node j’s strategy is [51](4)QSi⟵Sj=11+expZi-Zj/κ. The parameter κ denotes the rationality of the player in the game; when it comes close to zero, players will only learn the strategy, the revenue of which is higher than its own in this round. When κ increases, the probability of a player learning a low yield neighbor strategy will increase, which can be expressed by κ being 0 if Zj<Zi and 1 if Zi<Zj. When κ approaches ∝, this means that the player chooses completely random decision making.Each agent possesses one node in the evolutionary game. Assume that the number of nodes in the game network isN; the links between nodes can be represented by an adjacency matrixA with N order. If node j is the neighbor of node i, the matrix element aij=1; otherwise aij=0. The total payoff for node i can be expressed as follows:(5)Git=ai1SiTt·P·S1t+···+ai,i-1SiTt·P·Si-1t+ai,i+1SiTt·P·Si+1t+aiNSiTt·P·SNt, in which aij(j=1,…,i-1,i+1,…,N) denotes connection between agent i and its neighbor j, and aijSiT(t)·P·Sj(t)(j=1,,i-1,i+1,,N) denotes the total payoff of node i from the PD game with j, and t denotes the the total rounds that all agents implement PD game with their own neighbors. And Φi is the payoff matrix for node i, expressed as follows:(6)Φi=Fi1t1Fi,2t1⋯Fint1Fi1t2Fi,2t2⋯Fint2Fi1t3Fi,2t3⋯Fint3⋮⋮⋮⋮Fi1tmFi,2tm⋯Fi,ntm,then we solve the data information(7)Ai=ai1,…,ai,ai-1,ai,i+1,…,aiNT,and(8)Gx=Git1,Git2,⋯GitmT,where Fij(ti)=SiT·P·Sj(ti) and Eq. (6)–(8) satisfy the following equation: (9)Gi=Φi·Ai.In a similar fashion, through compressive sensing method, the remaining agents yield payoff from their neighbor-connection; the overall network adjacency matrix can be expressed asA=(A1,A2,…,An). Due to the sparsity of Ai, it is assured that it can be solved by using CS theory to get accurate results from partial time series data (η≡m/n, where η denotes the length of time series data, and m denotes the number of moment: for example, η=60% means that the number of used measurements equals 0.6N).


## 2.2. Network Model

A network can be denoted as an adjacent matrixW=(aij)N×N, which contains N nodes and E edges. In general, ki represents the degree of node i, and Ci represents the clustering coefficients of node i; it represents the ratio between the number of closed triplets and the total number of connected triplets of vertices; it can be calculated as follows:(10)Ci=1kiki-1∑j,k=1Naijajkaki, where aij=1 denotes that there exists a partnership between node i and j, so when aijajkaki=1, then a triangle forms among nodes i, j, k. The whole network clustering coefficient should be expressed as(11)C=1N∑i=1NCi.We validated our method by using PD games data occurring in Holme–Kim networks. Contrary to BA model, Holme–Kim model adds Triad Formation process (TF process), in order to change the principle when a new node is attached to an existing node by the principle called Preferential Attachment process (PA process). By this way, it not only makes the network growth mode more flexible, but also increases the clustering coefficient. In the Holme–Kim model, the evolution process of network has three driver factors: growth, preference attachment, and triad formation. The algorithm of the Holme–Kim model is shown as follows [52]:Growth. At the beginning, the network has m0 nodes; on each time step, one new node υ with m edges connects with the existing nodes (m⩽m0).Preferential Attachment. There is preference when the new node υ chooses other nodes to connect. The ratio of choosing node i depends on the degree of this node. It can be expressed as follows:(12)Πi=ki∑jkj.Triad Formation. After adding an edge between new node υ and i′s neighbor in the previous PA step, another neighbor node of i is chosen to connect with node υ with probability Pt. The network structure varies as Pt changes; Figure 1 shows the relationship between probabilities Pt and clustering coefficients CH of network. It is obvious that as Pt increases, CH grows as well, which implies that the network gets more closely.Figure 1
Correlation between theCH and Pt in Holme–Kim network.Another PD game data occurring in Newman-Watts small-world network (homogeneous small-world network) exhibits a homogeneous connectivity distribution, in the sense that the number of connections for all nodes is the same; the algorithm steps can be described as(1)
First, initializing a network withN nodes, it is ring-shaped; each node has 2k neighbors, k>0, k is an integer (usually small).(2)
Then adding an edge between the unconnected nodes with probabilityPN (0<PN≪1).Dunring the process, there will be multiple edges between any pair of nodes. All nodes will have no self-loops; the clustering coefficients of the network are denoted asCN.


## 3. Experimental Results

### 3.1. Generating Artificial Networks with Tunable Clustering Coefficient

The PD game is simulated on two types of networks, Holme–Kim networks and Newman-Watts small-world. To test the efficiency in reconstructing a network with our method, we first generate an artificial scale-free network with100 nodes by using Holme–Kim model and vary the Pt value from 0 to 1. The clustering coefficients (CH) are also incorporated into this range correspondingly. Then, without loss of generality, we set m0=m=5, N=100. We, especially, study the realtionship between SR, which measures the accuracy of network reconstruction, and the degree k in Holme–Kim networks. Each piece of data is averaged, performed on 10 networks by 10 runs. In order to reconfirm the performance of the algorithm, we set different network sizes to further investigate the performance. Analogously, we also reproduce a group of Newman-Watts small-world networks by using compressive sensing method to adjust their clustering coefficients into the same range. In order to uncover the topology structure of the evolution network, we record the strategies and payoffs in the form of time series as the system tends to the steady state.


### 3.2. Evaluation Criterion

PD game is implemented to investigate the performance of the network diffusion dynamics and structures; after recording the measurement matrixGi and measurement vector Φi, we introduce the SR to measure the performance; the accuracy rate can be expressed as follows:(13)SR=1N∑i=1NQir∩QioQio, in which Qio denotes neighbors of node i durning test set; Qir denotes the neighbors of node i durning training set. For a single player, SR denotes the ratio of the successfully predicted number of neighbor connections to the actual number of neighbors. At last, we get the average value for the whole network.


### 3.3. Results

Figure2(a) shows the SR of the network construction by means of L1-norm minimization, as shown in the picture; different CH indicate different topological structures of networks with tunable clustering coefficients; judging from transverse direction, the SR would increase along with the increase of CH value; the SR, especially, would reach the highest and would not get larger obviously when CH value gets close to 1. From the vertical perspective, the value of SR increases with the increase of η, for instance, the SR with which, when the length of data was 60%, is higher than that of 50%, and so forth. It demonstrates that we can use L1-norm minimization to reconstruct network effectively. Moreover, it is necessary to detail the progress of whole network reconstruction to infer local characteristic for each sigle node; we investigate the SR among single nodes, as shown in the subgraph in Figure 2(a). The bigger the degree for each node, the higher the SR. It indicates that the hub node has higher SR, which manifests that the node, which has the maximum degree, contributes to the accurate reconstruction.Figure 2
Success rate (SR) of networks with tunalbe clustering coefficientsCH in Holme–Kim model by means of L1-norm minimization. (a) The size is set to N=100, η is the length of data information, κ=0.1. As shown in the picture, when clustering coefficients CH increases, the accuracy SR increases. The tendency also applies in the variable value of η. Each piece of data is averaged, performed on 10 networks by 10 runs. The subgraph shows the relation between the SR and the degree of each game player, in which the network size is 100, η=50%. It shows that the bigger the degree of the node, the higher the SR. (b) is the performance of the SR for different network sizes, with N=100,150,200 respectively and η is fixed to 60%. When CH value increases, the SR increases correspondingly. SR decreases as the network size increases. (c) tests the SR with noise compared with that of original data; the Gaussian noise is defined as ε~[N(0,0.12)]. The size of the network is N=150, η=60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)Furthermore, in order to validateL1-norm minimization algorithm, we set different network sizes to further investigate the performance; we generate another two kinds of network size, which incorporates 150 nodes and 200 nodes, respectively. As shown in Figure 2(b), when the CH value increases, the SR increases correspondingly, but gets lower when the network size increases. From this point of view, we can coclude that the network size can influence the result of network reconstruction. For instance, when the CH=0.5, network size decreases from 150 to 100, then SR increases from 0.85 to 0.9, and so forth. The relationship between SR and network size is inversely related. In reality, noise exists everywhere in physical systems; the data get from complex systems are more or less influenced by noise. In order to further improve the experiment, Gaussian noises [N(0,0.12)] are added in the experiment (Q′=Q+ε, Q′ is the noise parameter) to investigate the stability of the result. Figure 2(c) indicates that the network size N is 150 and η=60%. We find that, compared with the data after adding the Gaussian noise, the accuracy of initial data is higher, although the CS method could reconstruct the missed links in the network.As a control group, we investigate the relationship between SR and clustering coefficientCN in Newman-Watts small-world network by means of L1-norm minimization, in which N=20,50,100 respectively. As shown in Figure 3(a) we can find that SR decreases as the clustering coefficients CN of the the network increase, which shows adverse tendency compared with Holme–Kim model. The main reason may be originating from the fact that the degree distribution in Newman-Watts small-world network is homogeneous; the nodes which have homogeneous degrees need similar data to reconstruct the network. The subgraph in Figure 3(b) shows the relation between the SR and degree distribution of each game player, in which the network size is N=100 and η=80%. It shows that the bigger the degree of the node, the lower the SR.Figure 3
(a) Correlation between the clustering coefficientsCN of the Newman-Watts small-world networks and SR by means of L1-norm minimization. N=50, η=50%,60%,70%,80%. (b) N=20,50,100, η is fixed to 60%. From the picture we can see that SR decreases as CN increases. The same with Holme–Kim model, when network size increases, SR tends to be lower. Each piece of data is averaged, performed on 10 networks by 10 runs. It shows that the bigger the degree of the node, the lower the SR. (c) tests the SR with noise compared with that of original data; the Gaussian noise is defined as ε~[N(0,0.12)]. The size of the network N=100, η=60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)The methods used to solve sparse approximation problems are available in a variety of ways. As we present ourL1-norm minimization algorithm in the above context of networks, we would like to compare the performance of our framework for network reconstruction with OMP [53], a greedy algorithm, which can be expressed as(14)minX0s.t.G=Φ·X,comparied with L1-norm minimization. OMP needs much more data and has lower accurcy [54]. The number of iterations required to find the correct support set determines the complexity of the algorithm. For the comparison, we carry out all experiments. The results are shown in Figures 4 and 5. The overall tendency is implemented by OMP in accordance with L1-norm minimization. In addition, the two methods are simultaneously implemented on scale-free networks and small-world netowrk, with data occurring in evolutionary games. As shown in Figures 6 and 7, we can find that the former proposed method is higher than or equal to OMP; for the Holme–Kim model network, the resulting SR in our method is higher than OMP; for the Newman-Watts small-world model, the resulting SR is nearly equal to OMP. The main reason may result from the fact that both L1-norm minimization and OMP can solve the problem of sparse signal recovery [55]. Both the L1-norm and orthogonal matching pursuit are the methods used to solve sparse approximation problems; by using L1-norm minimization method, it can get optimal solution to the problem of network reconstruction [56]. However, Newman-Watts small-world behaves much more sparse [57], as described in Table 1. These results demonstrate that two type networks can be efficiently inferred from limited measurements using L1-norm minimization method. In addition, we compare the two algorithms on the performance of convergence rate between two models as shown in Tables 2, 3, 4, and 5. In order to achieve high accuracy with different data length, the convergence rate is different. Compared with the L1-norm minimization, the OMP yields a faster computation speed; overall OMP is 1.2 times the computation speed of L1-norm minimization. Inspired by this, we may consider using OMP in small-world network. All the above demonstrate that the network topological structure influences the accuracy of network reconstruction. We should use a proper method to deal with the complex problem of network reconstruction.Table 1
The parameter for different network.
Type clustering coefficient modularity B-A big big W-S bigger smallTable 2
To achieve high accuracy (85%) the convergence rate was performed on scale-free network with two methods.
time/s N=100 N=150 N=200 N=250 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 784 653 1075 853 1283 1058 1462 1107 η=60% 923 842 1382 1191 1596 1227 1686 1340 η=70% 1080 818 1652 1458 1789 1503 2074 1773 η=80% 1425 1096 1893 1578 2056 1631 2261 1916Table 3
To achieve high accuracy (90%) the convergence rate was performed on scale-free network with two methods.
time/s N=100 N=150 N=200 N=250 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 803 676 1104 876 1309 1087 1497 1130 η=60% 945 869 1398 1209 1616 1250 1686 1378 η=70% 1109 840 1678 1483 1809 1528 2098 1799 η=80% 1445 1108 1914 1596 2076 1651 2279 1934Table 4
To achieve high accuracy (80%) the convergence rate was performed on small-world network with two methods.
time/s N=20 N=50 N=70 N=100 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 976 820 1180 984 1375 1100 1498 1247 η=60% 1195 1012 1416 1151 1564 1348 1207 1040 η=70% 1401 1120 1692 1421 1689 1407 1002 871 η=80% 1672 1416 1795 1504 1879 1527 864 701Table 5
To achieve high accuracy (85%) the convergence rate was performed on small-world network with two methods.
time/s N=20 N=50 N=70 N=100 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 998 832 1203 997 1397 1117 1512 1264 η=60% 1215 1032 1431 1171 1584 1360 1221 1062 η=70% 1420 1141 1709 1445 1700 1427 1029 901 η=80% 1692 1438 1815 1528 1899 1557 896 728Figure 4
(a) SR of networks with tunalbe clustering coefficientsCH in Holme–Kim model by OMP method, N=100, κ=0.1. It is obvious that SR behaves in accordance with L1-norm minimization. Each piece of data is averaged, performed on 10 networks by 10 runs. (b) is the performance of the SR for different network size, with N=100,150,200 respectively and η is fixed to 60%. When network size increases, SR tends to be lower. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b)Figure 5
Correlation between the clustering coefficientsCN of the Newman-Watts small-world networks and SR by OMP method. (a)N=50, η=60%,70%,80% (b)N=20,50,100, η is fixed to 60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b)Figure 6
Performance comparison ofL1-norm minimization with OMP on scale-free network, considering different values of η parameter and N=100,150,200. (a) N=100,η=60% (b) N=150,η=60% (c) N=200,η=80%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)Figure 7
Performance comparison ofL1-norm minimization with OMP on small-world network, considering different values of η parameter and N=50,70,100. (a) N=50,η=60% (b) N=70,η=60%. (c) N=100,η=90%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)


## 3.1. Generating Artificial Networks with Tunable Clustering Coefficient

The PD game is simulated on two types of networks, Holme–Kim networks and Newman-Watts small-world. To test the efficiency in reconstructing a network with our method, we first generate an artificial scale-free network with100 nodes by using Holme–Kim model and vary the Pt value from 0 to 1. The clustering coefficients (CH) are also incorporated into this range correspondingly. Then, without loss of generality, we set m0=m=5, N=100. We, especially, study the realtionship between SR, which measures the accuracy of network reconstruction, and the degree k in Holme–Kim networks. Each piece of data is averaged, performed on 10 networks by 10 runs. In order to reconfirm the performance of the algorithm, we set different network sizes to further investigate the performance. Analogously, we also reproduce a group of Newman-Watts small-world networks by using compressive sensing method to adjust their clustering coefficients into the same range. In order to uncover the topology structure of the evolution network, we record the strategies and payoffs in the form of time series as the system tends to the steady state.


## 3.2. Evaluation Criterion

PD game is implemented to investigate the performance of the network diffusion dynamics and structures; after recording the measurement matrixGi and measurement vector Φi, we introduce the SR to measure the performance; the accuracy rate can be expressed as follows:(13)SR=1N∑i=1NQir∩QioQio, in which Qio denotes neighbors of node i durning test set; Qir denotes the neighbors of node i durning training set. For a single player, SR denotes the ratio of the successfully predicted number of neighbor connections to the actual number of neighbors. At last, we get the average value for the whole network.


## 3.3. Results

Figure2(a) shows the SR of the network construction by means of L1-norm minimization, as shown in the picture; different CH indicate different topological structures of networks with tunable clustering coefficients; judging from transverse direction, the SR would increase along with the increase of CH value; the SR, especially, would reach the highest and would not get larger obviously when CH value gets close to 1. From the vertical perspective, the value of SR increases with the increase of η, for instance, the SR with which, when the length of data was 60%, is higher than that of 50%, and so forth. It demonstrates that we can use L1-norm minimization to reconstruct network effectively. Moreover, it is necessary to detail the progress of whole network reconstruction to infer local characteristic for each sigle node; we investigate the SR among single nodes, as shown in the subgraph in Figure 2(a). The bigger the degree for each node, the higher the SR. It indicates that the hub node has higher SR, which manifests that the node, which has the maximum degree, contributes to the accurate reconstruction.Figure 2
Success rate (SR) of networks with tunalbe clustering coefficientsCH in Holme–Kim model by means of L1-norm minimization. (a) The size is set to N=100, η is the length of data information, κ=0.1. As shown in the picture, when clustering coefficients CH increases, the accuracy SR increases. The tendency also applies in the variable value of η. Each piece of data is averaged, performed on 10 networks by 10 runs. The subgraph shows the relation between the SR and the degree of each game player, in which the network size is 100, η=50%. It shows that the bigger the degree of the node, the higher the SR. (b) is the performance of the SR for different network sizes, with N=100,150,200 respectively and η is fixed to 60%. When CH value increases, the SR increases correspondingly. SR decreases as the network size increases. (c) tests the SR with noise compared with that of original data; the Gaussian noise is defined as ε~[N(0,0.12)]. The size of the network is N=150, η=60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)Furthermore, in order to validateL1-norm minimization algorithm, we set different network sizes to further investigate the performance; we generate another two kinds of network size, which incorporates 150 nodes and 200 nodes, respectively. As shown in Figure 2(b), when the CH value increases, the SR increases correspondingly, but gets lower when the network size increases. From this point of view, we can coclude that the network size can influence the result of network reconstruction. For instance, when the CH=0.5, network size decreases from 150 to 100, then SR increases from 0.85 to 0.9, and so forth. The relationship between SR and network size is inversely related. In reality, noise exists everywhere in physical systems; the data get from complex systems are more or less influenced by noise. In order to further improve the experiment, Gaussian noises [N(0,0.12)] are added in the experiment (Q′=Q+ε, Q′ is the noise parameter) to investigate the stability of the result. Figure 2(c) indicates that the network size N is 150 and η=60%. We find that, compared with the data after adding the Gaussian noise, the accuracy of initial data is higher, although the CS method could reconstruct the missed links in the network.As a control group, we investigate the relationship between SR and clustering coefficientCN in Newman-Watts small-world network by means of L1-norm minimization, in which N=20,50,100 respectively. As shown in Figure 3(a) we can find that SR decreases as the clustering coefficients CN of the the network increase, which shows adverse tendency compared with Holme–Kim model. The main reason may be originating from the fact that the degree distribution in Newman-Watts small-world network is homogeneous; the nodes which have homogeneous degrees need similar data to reconstruct the network. The subgraph in Figure 3(b) shows the relation between the SR and degree distribution of each game player, in which the network size is N=100 and η=80%. It shows that the bigger the degree of the node, the lower the SR.Figure 3
(a) Correlation between the clustering coefficientsCN of the Newman-Watts small-world networks and SR by means of L1-norm minimization. N=50, η=50%,60%,70%,80%. (b) N=20,50,100, η is fixed to 60%. From the picture we can see that SR decreases as CN increases. The same with Holme–Kim model, when network size increases, SR tends to be lower. Each piece of data is averaged, performed on 10 networks by 10 runs. It shows that the bigger the degree of the node, the lower the SR. (c) tests the SR with noise compared with that of original data; the Gaussian noise is defined as ε~[N(0,0.12)]. The size of the network N=100, η=60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)The methods used to solve sparse approximation problems are available in a variety of ways. As we present ourL1-norm minimization algorithm in the above context of networks, we would like to compare the performance of our framework for network reconstruction with OMP [53], a greedy algorithm, which can be expressed as(14)minX0s.t.G=Φ·X,comparied with L1-norm minimization. OMP needs much more data and has lower accurcy [54]. The number of iterations required to find the correct support set determines the complexity of the algorithm. For the comparison, we carry out all experiments. The results are shown in Figures 4 and 5. The overall tendency is implemented by OMP in accordance with L1-norm minimization. In addition, the two methods are simultaneously implemented on scale-free networks and small-world netowrk, with data occurring in evolutionary games. As shown in Figures 6 and 7, we can find that the former proposed method is higher than or equal to OMP; for the Holme–Kim model network, the resulting SR in our method is higher than OMP; for the Newman-Watts small-world model, the resulting SR is nearly equal to OMP. The main reason may result from the fact that both L1-norm minimization and OMP can solve the problem of sparse signal recovery [55]. Both the L1-norm and orthogonal matching pursuit are the methods used to solve sparse approximation problems; by using L1-norm minimization method, it can get optimal solution to the problem of network reconstruction [56]. However, Newman-Watts small-world behaves much more sparse [57], as described in Table 1. These results demonstrate that two type networks can be efficiently inferred from limited measurements using L1-norm minimization method. In addition, we compare the two algorithms on the performance of convergence rate between two models as shown in Tables 2, 3, 4, and 5. In order to achieve high accuracy with different data length, the convergence rate is different. Compared with the L1-norm minimization, the OMP yields a faster computation speed; overall OMP is 1.2 times the computation speed of L1-norm minimization. Inspired by this, we may consider using OMP in small-world network. All the above demonstrate that the network topological structure influences the accuracy of network reconstruction. We should use a proper method to deal with the complex problem of network reconstruction.Table 1
The parameter for different network.
Type clustering coefficient modularity B-A big big W-S bigger smallTable 2
To achieve high accuracy (85%) the convergence rate was performed on scale-free network with two methods.
time/s N=100 N=150 N=200 N=250 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 784 653 1075 853 1283 1058 1462 1107 η=60% 923 842 1382 1191 1596 1227 1686 1340 η=70% 1080 818 1652 1458 1789 1503 2074 1773 η=80% 1425 1096 1893 1578 2056 1631 2261 1916Table 3
To achieve high accuracy (90%) the convergence rate was performed on scale-free network with two methods.
time/s N=100 N=150 N=200 N=250 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 803 676 1104 876 1309 1087 1497 1130 η=60% 945 869 1398 1209 1616 1250 1686 1378 η=70% 1109 840 1678 1483 1809 1528 2098 1799 η=80% 1445 1108 1914 1596 2076 1651 2279 1934Table 4
To achieve high accuracy (80%) the convergence rate was performed on small-world network with two methods.
time/s N=20 N=50 N=70 N=100 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 976 820 1180 984 1375 1100 1498 1247 η=60% 1195 1012 1416 1151 1564 1348 1207 1040 η=70% 1401 1120 1692 1421 1689 1407 1002 871 η=80% 1672 1416 1795 1504 1879 1527 864 701Table 5
To achieve high accuracy (85%) the convergence rate was performed on small-world network with two methods.
time/s N=20 N=50 N=70 N=100 data length l 1 OMP l 1 OMP l 1 OMP l 1 OMP η=50% 998 832 1203 997 1397 1117 1512 1264 η=60% 1215 1032 1431 1171 1584 1360 1221 1062 η=70% 1420 1141 1709 1445 1700 1427 1029 901 η=80% 1692 1438 1815 1528 1899 1557 896 728Figure 4
(a) SR of networks with tunalbe clustering coefficientsCH in Holme–Kim model by OMP method, N=100, κ=0.1. It is obvious that SR behaves in accordance with L1-norm minimization. Each piece of data is averaged, performed on 10 networks by 10 runs. (b) is the performance of the SR for different network size, with N=100,150,200 respectively and η is fixed to 60%. When network size increases, SR tends to be lower. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b)Figure 5
Correlation between the clustering coefficientsCN of the Newman-Watts small-world networks and SR by OMP method. (a)N=50, η=60%,70%,80% (b)N=20,50,100, η is fixed to 60%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b)Figure 6
Performance comparison ofL1-norm minimization with OMP on scale-free network, considering different values of η parameter and N=100,150,200. (a) N=100,η=60% (b) N=150,η=60% (c) N=200,η=80%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)Figure 7
Performance comparison ofL1-norm minimization with OMP on small-world network, considering different values of η parameter and N=50,70,100. (a) N=50,η=60% (b) N=70,η=60%. (c) N=100,η=90%. Each piece of data is averaged, performed on 10 networks by 10 runs.
(a) (b) (c)


## 4. Conclusion

In our study, we investigate the effect on the accuracy of the network reconstruction byL1-norm minimization method with different topological structures of networks, measured by variable clustering coefficients among two types of network models: one is scale-free network and the other is small-world network. First, we construct two types of network models with variable clustering coefficients, then we reconstruct the network based on the evolutionary-game data by L1-norm minimization method. We find that the success rate of the two kinds of network performs differently; for Holme–Kim (scale-free) network, the success rate increases correspondingly when the clustering coefficients CH increase but decreases when the clustering coefficients CN increase in the Newman-Watts (small-world network). The explanation can be derived from the fact that, in Holme–Kim model, the bigger the degree for each node, the lower the success rate, while the small-world behaves opposite. Meanwhile, both of the success rates for the two network models decrease as the network size increases. At last, we adopt OMP method to reconstruct network. The results show that the SR carried out by L1-norm minimization method is higher than or at least equal to OMP, and the accuracy rate of L1-norm minimization method is 10% higher than that of OMP. Meanwhile, OMP is 1.2 times the convergence rate of L1-norm minimization. From the above, we can conclude that the network structure has influence on the accuracy of the network reconstruction by compressive sensing method.Our method, mentioned in the paper, can be adopted to reconstruct sparse networks among the real-world networks for the reason that small-world phenomenon and scale-free characteristics are two typical complex network characteristics. Our contribution to the current literature can be summarized as follows: the method metioned above needs time series data; usually the topology structure of the network cannot be abtained. From this point of view, if we do not know about the topology structure, we may first chooseL1-norm minimization method; if we know the topology structure of the network, the network has the same characteristics as Holme-Kim model (scale-free characteristics); we may be more likely to choose L1-norm minimization; if the network has the same properties as the small-world network, for the accuracy recovery by L1-norm minimization is nearly equal to that of OMP, we can adopt both of these methods; however, OMP method has an advantage over L1-norm minimization from a convergence speed perspective, so if we consider the speed of convergence, we may choose OMP method. Overall, our methods, in principle, are applicable in real-world such as protein network, Internet network. Meanwhile, the research also puts forward application of CS in other research fields, such as remote sensing and social networks.Meanwhile, there exist some shortcomings in this paper, which may influence the further research for network reconstruction. First, the two methods mentioned in this paper are used to recover sparse network; better methods are worth exploring [58, 59]. Second, we only investigate the effect of compressive sensing depending on dynamic clustering coefficients of the macro network structure. More characteristics should be considered such as betweenness, closeness, and eigenvector centrality to verify our methods. In addition, we should also consider the micro network structure, such as Ring, Chain, and Star, which may affect the result [60]. Third, in this paper, we consider only two phenomena: one is the small-world, and the other is scale-free network, but in the actual network there are both scale-free network and small world network natures of the network, so it is possible that the two methods may not effectively reconstruct the network; we should find a better way. Last, during the process of simulation, all the data are observable. In fact, the measurement can be obtained partially [61, 62]; that is to say, some hidden nodes cannot be got in the system. How to implement our methods in these situations deserves to be studied further.Generally speaking, this paper puts forward two methods to deal with the problem of network reconstruction through two different manners. It provides directions for us to reconstruct complex network; yet it is expected to make efforts to pursue better approaches. All these deserved to be explored.



---

*Source: 4949673-2018-10-24.xml*