# Predicting the Robustness of Large Real-World Social Networks Using a Machine Learning Model

Authors: Ngoc-Kim-Khanh Nguyen; Quang Nguyen; Hai-Ha Pham; Thi-Trang Le; Tuan-Minh Nguyen; Davide Cassi; Francesco Scotognella; Roberto Alfieri; Michele Bellingeri
Journal: Complexity
 (2022)

---

## Abstract

Computing the robustness of a network, i.e., the capacity of a network holding its main functionality when a proportion of its nodes/edges are damaged, is useful in many real applications. The Monte Carlo numerical simulation is the commonly used method to compute network robustness. However, it has a very high computational cost, especially for large networks. Here, we propose a methodology such that the robustness of large real-world social networks can be predicted using machine learning models, which are pretrained using existing datasets. We demonstrate this approach by simulating two effective node attack strategies, i.e., the recalculated degree (RD) and initial betweenness (IB) node attack strategies, and predicting network robustness by using two machine learning models, multiple linear regression (MLR) and the random forest (RF) algorithm. We use the classic network robustness metricR as a model response and 8 network structural indicators (NSI) as predictor variables and trained over a large dataset of 48 real-world social networks, whose maximum number of nodes is 265,000. We found that the RF model can predict network robustness with a mean squared error (RMSE) of 0.03 and is 30% better than the MLR model. Among the results, we found that the RD strategy has more efficacy than IB for attacking real-world social networks. Furthermore, MLR indicates that the most important factors to predict network robustness are the scale-free exponent α and the average node degree <k>. On the contrary, the RF indicates that degree assortativity a, the global closeness, and the average node degree <k> are the most important factors. This study shows that machine learning models can be a promising way to infer social network robustness.


---

## Body

## 1. Introduction

The study of the social network from a complexity science perspective has attracted much interest recently [1]. Especially, the study of dynamic processes that take place in these complex networks can have various applications. For example, the study of network robustness, i.e., “network robustness” is the capacity of a network to hold its functionality when a proportion of nodes/edges are removed, can help attack a network efficiently, or inversely design a more robust network structure in practice [2–7]. On the other hand, the study of epidemic processes that take place in the network can be used to spread the news [8–12], optimize vaccination strategy [13–15], or define a better social-distancing rule [16–19].Besides a few simple model networks where analytical models can be developed [20–24], most of the studies rely on computer simulations. For example, for the study of the network’s robustness, node/edge removal Monte-Carlo simulations are usually employed. In such a process, nodes/edges are sequentially removed from the network using computer simulations. A “robustness” metric is then recorded at each step of the removal process. The most commonly used robustness metric is the largest connected component (LCC) of the remaining network [25].The way nodes/edges are selected to be removed is called the removal strategy or attack strategy. One can classify attack strategies into two types, initial and recalculated attack strategies. For an initial attack strategy, nodes/edges are removed according to a node/edge ranking that is computed ahead of the removal simulation. In contrast for a recalculated attack strategy, the ranking is updated after each node/edge removal [4].For node removal attack strategies, the node ranking is usually computed using node centrality measures such as degree [26, 27], closeness [4], and betweenness [7, 30]. It was found that for social networks, the recalculated betweenness node attack strategy (RB) is, on average, the most effective node attack strategy to dismantle the network [2, 7, 28, 29]. Other effective strategies are the recalculated degree (RD) and the initial betweenness (IB) [7, 28, 30].Because of the sequential nature of the removal process, the node removal simulation is computationally costly, especially for recalculated strategies. For example, a simulation using an RD attack strategy has a time complexity ofO (N × E), where N is the number of nodes and E is the number of edges of the network. The reason is that the node removal process has an N step, and at each step, a degree ranking is computed taking a time that scales with E. However, for RB, the computation of the whole network’s betweenness is known to be very computationally costly, due to the definition of the network’s node betweenness [31, 32]. The most efficient known algorithm for calculating network betweenness is the Brandes algorithm [33], which has a time complexity of O (N × E). In consequence, the whole node removal process using IB and RB attack strategies can have a time complexity of O (N × E) and O (N2 × E), respectively. Although the IB attack strategy has the same time complexity as the RD attack strategy, the RB’s time complexity is much higher. For illustration, in Figure 1, we present the total simulation time tIB and tRD for the corresponding attack strategies IB and RD, respectively, for all our studying social networks (48 networks see Section 2). In addition, we present the total simulation time tRB for the attack strategy RB for 4 networks (insert graph) as an example, as a function of the productN × E. We found a good linear relationship between tIB and tRD and N × E for all networks as expected, and tRB is about two orders of magnitude higher than tIB and tRD, for networks of equal N × E.Figure 1
Computation time of a complete Monte Carlo network node attack simulation for all studied real-world social networks (using initial betweenness (IB) and recalculated degree (RD) attack strategy) and for 4 networks (using recalculated betweenness strategy (RB)) as a function of the productN × E (node number (N) edge number (E). We found that tIB and tRD scale approximately linearly with respect to the product N × E, while tRB scales linearly with respect to the product N2 × E (insert graph). From this result, we can estimate that the RB simulation time for the largest networks in our dataset will take more than 50 days using the same hardware.The simulation time can become an issue for the cases of social networks because their size can be extremely large. In fact, to our knowledge, most studies of dynamic processes on social networks that use an RB attack strategy only consider small-size real-world social networks of less than 100,000 nodes [7, 28, 30]. For very large social networks, the RB node attack strategy can take an unrealistic amount of time. Therefore, RB is not suitable for large social networks for an average computer station. One possibility is to use the alternative betweenness-based attack strategy with only one betweenness calculation, namely, the initial betweenness attack strategy IB, together with other recalculated strategies that use another node centrality metric that is less computationally costly. In consequence, in this work, we consider two candidate attack strategies for breaking large real-world social networks, IB and RD attack strategies. Besides the comparative study between different network node attack strategies, other works focused on the relationship between network robustness and network structural indicators (NSIs). Iyer et al. [4] studied network robustness as a function of the node clustering coefficient (or node transitivity). The research on model networks with tunable clustering coefficients demonstrates that networks with higher clustering coefficients are more robust, with the most important effect for the node degree and node betweenness attack [4]. Nguyen and Trang [34] studied Facebook social networks and found that those networks with higher modularity Q have lower robustness to node removal. The modularity indicator Q introduced by Newman and Girvan [35] measures how well a network breaks into communities, (i.e., a community or module in a network is a well-connected group of nodes that have sparser connections with nodes outside the group). In [29], the authors empirically analyzed how the modularity of scale-free models and real-world social networks affects their robustness and the relative efficacy of different node attack strategies. The abovementioned studies analyzed the relationship between network robustness and a single NSI.On the other hand, machine learning (ML) is a technique that has seen a huge breakthrough in the last decade, beating state-of-the-art results in many prediction applications [36]. It initially solved technical problems in computer vision and natural language processing [37–39] and then expanded into many other fields such as health care, finance, manufacturing, energy, and environment. The key characteristic of an ML model is the ability to intelligently learn nonlinear relationships between the input and output without explicitly knowing them.In this work, given such a complex relationship between network robustness and NSIs, we adopted a method from machine learning in order to learn such a complexity. Our main contribution is the application of the ML model to predict real-world social network robustness with acceptable errors. We develop ML models to predict network robustness under two main attack strategies, the IB and RD attack strategies, independently. We also implemented three popular ML models, single-variable linear regression, multiple-variable linear regression, and random forest models. Our results demonstrate that a data-driven method such as ML can be an efficient way to study the network’s complexity.Our work comprises three steps: (1) collect a real-world network dataset and compute NSIs; (2) run Monte Carlo node attack simulations to estimate network robustness; (3) build and evaluate a model that predicts network robustness from their NSIs. The paper is organized as follows: in Section2, we describe our dataset of 48 real-world social networks. In Section 3, we describe the network robustness Monte Carlo simulation method and three ML models for predicting the network robustness, i.e., simple and multiple linear regression (SLR and MLR, respectively) and random forest (RF) model. Section 4 presents the main results, and finally, we discuss and conclude in Section 5.


## 2. Real-World Social Network Datasets and Robustness Estimation

Real-world social networks are downloaded from two sources: the Stanford Large Network Dataset Collection (https://snap.stanford.edu/data/) and the Network Repository social networks (https://networkrepository.com/soc.php). We select 48 social networks with a node number (N) ranging over five orders of magnitude. The smallest network is the “Twitch user-user network of gamers who stream in Portugal” having N = 1,914, and the largest network is the “e-mail network from an EU research institution” with N = 265,216. However, the network with the largest number of edges (E) is the “BlogCatalog social blog” with E = 4,186,390. The social networks used in this study are unweighted (i.e., we do not take into account edge weights) and undirected (we do not consider edge directionality).Table1 summarizes 48 real-world social networks and their NSIs. Besides N and E, we also compute the following NSIs:(i)
Network density <k> is the average node degree, i.e., the average number of edges per node.(ii)
Fitted scaled-free exponent (α): we assume that all social network degree distributions follow a power law of P(k) ∼ k−α where k is the node degree. The power exponent value α is fitted using the ordinary least squared method. From this fitting, we also extract the fitting variance of α, denoted by α2.(iii)
Assortativity (a): the assortativity coefficient is a Pearson correlation coefficient of the degree between pairs of linked nodes [40], which varies between −1 and 1. A positive value of a indicates a preferential connection between nodes of a similar degree, while negative values indicate that nodes of different degree have more change to connect.(iv)
Modularity (Q) : The modularity indicator Q calculates how a network can be partitioned into subnetworks (modules or communities):(1)Q=12E∑i,jaij−kikj2Eδci,cj,whereE is the number of edges, aij is the element of the adjacency matrix A in the row i and column j, ki is the degree of i, kj is the degree of j, ci is the module (or community) of i, cj that of j, the sum goes over all i and j pairs of nodes, and δ(x, y) is 1 if x = y and 0 otherwise [13].(v)
Global clustering coefficient (C): the global clustering coefficient (C) is based on triplets of nodes. A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected edges. The global clustering coefficient is the number of closed triplets (or 3x triangles because a triangle comprises 3 overlapping triplets, each centered at one of the three nodes) over the total number of triplets (both open and closed). The formula is as follows:(2)C=λclosedλtotal,whereλclosed is the number of closed triplets and λtotal is the total number of triplets in the network. The global clustering coefficient represents the overall probability for the network to have adjacent nodes interconnected, thus making more tightly connected modules [41].(vi)
Average closeness (Cl) is the average of all network nodes’ closeness, where the closeness (or closeness centrality) of a node is calculated as the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph [42, 43]:(3)Cl=C¯li=1N∑i=1NCli,withCli=1∑j≠idi,j,whereN is the number of nodes and d(i, j) is the length of the shortest path between nodes i and j.Table 1
Structural statistics of real-world social networks: node (N), edge (E), average node degree <k>, fitted power-law exponent α, the fitting variance of the power law exponent α2, assortativity coefficient a, modularity Q, global clustering coefficient C, and average node closeness Cl.
NbNetwork descriptionShortnameNE<k>αα2aQCCl1Blue verified Facebook page networks of artist categoryArtist50,515819,30632.41.9375.4370.0020.1770.0530.2752Blue verified Facebook page networks of athlete categoryAthlete13,86886,85912.52.1304.7780.0050.5470.1290.2373Blue verified Facebook page networks of company categoryCompany14,11552,3117.41.9954.1910.0220.6320.1530.1934Blue verified Facebook page networks of government categoryGovernment7,05989,45625.31.8294.4010.0040.4780.2240.2705Blue verified Facebook page networks of new site categorynew_sites27,919206,26014.82.0975.0820.0090.5090.1140.2336Blue verified Facebook page networks of politician categoryPolitician5,91041,73014.12.0584.4740.0050.6600.3010.2197Blue verified Facebook page networks of public figure categorypublic_figure11,56767,11511.61.8414.2120.0090.4410.1670.2218Blue verified Facebook page networks of tV show categoryTvshow3,89417,2638.91.6223.2790.0370.7700.5910.1669Citation NW of arXiv High Energy Physics (phenomenology) paperCit-HepPh34,548421,57924.42.5286.3100.0030.4720.1460.23710Citation NW of arXiv High Energy Physics (theory) paperCit-HepTh27,772352,80825.41.9165.0060.0060.4240.1200.00011Collaboration network of arXiv astro physicsCA-AstroPh18,774396,16142.22.1746.0210.0500.4120.3160.00012Collaboration network of arxiv condensed matterCA-CondMat23,135186,93716.22.5846.2350.0740.6490.2580.24513Collaboration network of arxiv general relativityCA-GrQc5,24428,98111.12.2904.8950.1920.7810.6110.00014Collaboration network of arxiv high energy physicsCA-HepPh12,010237,01139.51.4074.0130.1030.3830.6570.00015Collaboration network of arxiv high energy physics theoryCA-HepTh9,87951,97210.53.3066.9070.0800.7080.2720.00016Deezer’s users friendship networks from Croatiadeezer_HR54,575498,20318.33.4617.9540.0050.5250.1150.22417Deezer’s users friendship networks from Hungarydeezer_HU47,540222,8889.44.4358.5250.0080.5800.0930.18918Deezer’s users friendship networks from Romaniadeezer_RO41,775125,8276.03.3926.4020.0080.6820.0750.16019E-mail communication network from enronEmail-enron36,694367,66320.01.4464.2130.0360.3330.0850.30720E-mail network from a EU research institutionEmail-EuAll265,216420,0463.20.6461.901−0.0390.0470.0070.00021Follower relationships network of European users from deezerdeezer_Europe28,28392,7536.62.9815.9720.0110.6030.0960.15922Network of trusting consumers from the review site Epinions.comSoc-Epinions175,881508,83813.41.5124.2890.0010.2470.0820.23723Page-page network of verified facebook sitesmusae_facebook22,472171,00315.22.0294.9450.0110.6300.2320.20624Slashdot social network from February 2009Slashdot090282,170948,46523.11.6174.7280.0800.2020.0260.25025Slashdot social network from November 2008Slashdot081177,362905,46923.41.6034.6850.0830.2070.0260.25226Social network of github developers.musae_git37,702289,00415.31.2673.482−0.0010.1520.0120.31427Social network of LastFM users from asia.lastfm_Asia7,62627,8077.31.8073.7300.0060.6790.1790.19528Twitch user-user networks of gamers who stream in Englishmusae_ENGB7,12835,3259.91.2042.7700.0010.2670.0420.27729Twitch user-user networks of gamers who stream in Frenchmusae_FR6,551112,66734.41.3033.392−0.0010.0840.0540.37830Twitch user-user networks of gamers who stream in Germanmusae_DE9,500153,13932.21.3053.476−0.0010.0620.0460.37431Twitch user-user networks of gamers who stream in Portugalmusae_PTBR1,91431,30032.71.1272.680−0.0030.0810.1310.40232Twitch user-user networks of gamers who stream in Russianmusae_RU4,38737,30517.01.0542.522−0.0030.1010.0490.33733Twitch user-user networks of gamers who stream in Spainmusae_ES4,65059,38325.51.3273.233−0.0010.1090.0840.35234Wikipedia page-to-page networks on chameleon topicmusae_chameleon2,27936,10231.70.9742.3810.0060.2030.4450.29135Wikipedia page-to-page networks on crocodile topicmusae_crocodile11,633180,02131.00.8922.483−0.0100.1810.0390.31636Wikipedia page-to-page networks on squirrel topicmusae_squirrel5,203217,07483.40.7482.245−0.0010.0720.4510.33537Wikipedia who-votes-on-whom networkWiki-vote7,117103,69029.11.4123.644−0.0010.0250.1360.31838BlogCatalog social blogBlogCatalog188,7844,186,39094.32.2659.866−0.0010.0180.0600.33139BlogCatalog social blog version 2BlogCatalog297,8842,043,70141.82.1419.330−0.0010.0060.0570.35540BlogCatalog social blog version 3BlogCatalog310,312333,98364.81.9296.939−0.0010.0260.0910.42441Douban online social networkDouban154,908654,1888.43.94610.755−0.0480.0930.0100.19542Gowalla location-based social networkingGowalla196,591950,3279.71.3865.3370.0060.5010.0230.22143TheMarker cafe online social networkTheMarker69,4131,644,84947.42.5479.7990.0000.0220.0460.33244Brightkite location-based online social networkBrightkite58,228214,0787.42.3306.8020.0050.5390.1110.22445The friendships network between users of the websitehttp://www.hamsterster.comHamsterster2,42616,63013.72.5996.0510.0670.3940.2310.40446A google-plus subgraphSoc-gplus23,62839,2423.31.1884.021−0.068−0.0270.0040.25147Anybeat online social networkAnybeat12,64567,05310.60.9223.294−s0.0090.1330.0180.32348Advogato online social networkAdvogato6,55151,33215.72.0645.7850.0780.3120.1110.000


### 2.1. Network Robustness Monte Carlo Simulation

For each network, we run two node removal processes using Monte-Carlo simulations. Nodes are removed consecutively following the ranking of initial betweenness (IB) and the ranking of the recalculated degree (RD). In the case of ties, e.g., nodes with an equal betweenness or degree score, we removed one of them at random. After each node removal, we compute the network robustness measure and the relative size of the largest connected component LCC, together with the accumulated proportion of nodes removedq. Finally, we obtain two curves LCC (q) corresponding to two node removal processes, IB and RD. The whole simulation is repeated 10 times, and the final curves LCC (q) are the average results.In addition, we compute a single value defined as the network robustness (R), as performed by Bellingeri et al. [44], and the area below the normalized LCC curve during the removal process, R =  LCCq¯. R therefore can be between two theoretical extremes, R≃0 (absolute fragile network) and R≃0.5 (absolute robust network). We denote RRD and RIB as the network robustness against RD and IB node attack strategies, respectively.In summary, we collect 48 real-world social networks, and then, we compute 9 NSIs for each network as inputs. In parallel, we run Monte Carlo simulations and obtain the robustness represented by two metrics, RRD and RIB. The higher they are, the more robust the network is. Those two metrics are the output of each network and will be predicted using ML models.


## 2.1. Network Robustness Monte Carlo Simulation

For each network, we run two node removal processes using Monte-Carlo simulations. Nodes are removed consecutively following the ranking of initial betweenness (IB) and the ranking of the recalculated degree (RD). In the case of ties, e.g., nodes with an equal betweenness or degree score, we removed one of them at random. After each node removal, we compute the network robustness measure and the relative size of the largest connected component LCC, together with the accumulated proportion of nodes removedq. Finally, we obtain two curves LCC (q) corresponding to two node removal processes, IB and RD. The whole simulation is repeated 10 times, and the final curves LCC (q) are the average results.In addition, we compute a single value defined as the network robustness (R), as performed by Bellingeri et al. [44], and the area below the normalized LCC curve during the removal process, R =  LCCq¯. R therefore can be between two theoretical extremes, R≃0 (absolute fragile network) and R≃0.5 (absolute robust network). We denote RRD and RIB as the network robustness against RD and IB node attack strategies, respectively.In summary, we collect 48 real-world social networks, and then, we compute 9 NSIs for each network as inputs. In parallel, we run Monte Carlo simulations and obtain the robustness represented by two metrics, RRD and RIB. The higher they are, the more robust the network is. Those two metrics are the output of each network and will be predicted using ML models.


## 3. Machine Learning Approach

This section presents the details of SLR, MLR, and RF models.


### 3.1. Simple Linear Regression Model (SLR)

Linear regression is the simplest model for prediction. The SLR model between the network robustnessR and an NSI x is expressed by the linear equation:(4)R=a0+a1x,where a0 is the intercept and a1 is the slope. In (4), an ordinary least square (OLS) is applied for estimating coefficients by minimizing an appropriate loss function [45, 46]. Once the OLS process, which is also called the fitting process, is performed, we can use (1) to predict the robustness R of a new network for a given indicator x. In addition, we derive a statistics t-test from the OLS process with the null hypothesis H0: a1 = 0. A rejection of H0 means that there is a significant linear relationship between R and the NSI x.We run the SLR model fit for all NSIs listed in Table1 excluding E because it can be expressed in terms of two other NSIs : E = N < k>/2.


### 3.2. Multiple Linear Regression Model

Multiple linear regression (MLR) is an extension of SLR for multidimension variablesx = (x1, x2, …, xn), where x1, x2, …, xn are NSIs. The linear equation between network robustness R and NSIs is as follows:(5)R=a0+a1x1+a2x2+⋯+anxn,where ai are coefficients obtained from the OLS method.


### 3.3. Random Forest Model

The random forest (RF) belongs to the ensemble class of ML models, indicating that it aggregates the prediction from an ensemble of ML base models, here, decision tree regression (DTR) models. We briefly describe the DTR in the following section.A DTR starts with the root of the tree containing all samples (48 networks in our case). It then splits into two different nodes by selecting samples whose value of a certain variable is higher or lower than a certain threshold value. Figure2(a) represents a basic decision tree diagram for our dataset. The root node containing 48 networks splits into two other nodes by considering whether the variable (NSI in our case) scale-free exponent α is higher or lower than 2.5.Figure 2
(a) An example of a decision tree: the root node containing 48 networks splits into two other nodes, Node 11 and Node 12, with 13 and 35 networks, respectively, according to the value of the scale-free exponentα. Then, Node 12 splits into two other nodes, Node 21 and Node 22, with 15 and 20 networks, respectively, according to the value of the network density <k>. We assume that at Node 11, Node 21, and Node 22, no split is possible because of a certain stopping rule, and thus, they become final leaves. In general, any NSI can be used to divide networks at any split, and the decision tree can be arbitrarily complex depending on the stopping rule. (b) An illustration of the same decision tree in the 2-dimension (α and <k>) space with final leaves.
(a)(b)The DTR selects the variable, and its splitting value is based on information theory, in concrete considering the entropy concept. Entropy is a metric of uncertainty of a node. The DTR splits a node by maximizing the information gain, which is the weighted difference between the total entropy of two resulting nodes and the entropy of the initial node. The DTR successively splits until a stopping condition is reached, for example if the size of the current node is smaller than 20. The final node is also called a leaf node. In Figure2(a), after the first split of the root, the left child node becomes a leaf node, while the right child node continues to split into two leaf nodes.Once the final DTR is obtained, it can be used to predict the value of a new sample as follows. The new sample will be classified into one of the leaves, and its prediction value will be the average value of all the samples that are classified into the same leaf.Finally, the RF model creates multiple decision trees randomly drawn from the data, usually several hundred, and averaging the results from all trees to output a new result often leads to strong predictions [47, 48].The decision tree can fit nonlinear datasets because it can split the same NSI multiple times. However, decision tree is easy to be overfitting, i.e., it is too sensitive to the training data while failing to predict new coming (testing) data. In order to address this problem, a random forest (RF) model is obtained by creating multiple randomly drawn decision trees from data, usually several hundred. The final regression prediction will be the average prediction of all the decision trees [47–49] (in this work, we implement an RF with 300 DTRs). Using an RF, “feature importance” measurement can be derived to rank the NSI [50].


### 3.4. Data Preparation, Validation, and Performance Evaluation

All NSIs can be computed from the network’s data, and thus, our dataset did not contain missing values. We also excludeE because of redundancy as mentioned above. The other 8 NSIs are normalized to avoid large differences in the indicators’ range:(6)xi,j′=xi,j−x¯iσxi,where xi,j is the value of the NSI i for observation (network) j and x¯i and σxi are the mean and the standard deviation of the NSI i, respectively.In the first step, we use the whole dataset to build ML models and compare the results between models and two target variables. However, due to overfitting problems in many ML models, the model’s performance for new data is not always coherent as that in the training step, and we need to validate models in the second step. We choose the leave-one-out validation [51]. In this way, we train each of the above models 48 times: each time the whole dataset excluding one observation is used to train the model, and then, the model is used to predict the target value of the remaining (hold-out) observations and repeats for each of 48 hold-out observations. The overall evaluation result is the average across all 48 regressions.It is noted that for the SLR model, we only consider regression coefficients in order to analyze the dependence of robustness metrics with respect to each NSI. However, for MLR and RF models, we analyze the prediction of robustness metrics using four common evaluation metrics for regression problems, the root mean square error (RMSE) and the coefficient of determination (also named the explained variance ratio,R2) as analytical metrics and the frequency distribution and the Q-Q plot of residual errors as graphical metrics.RMSE is the square root of the summation of the squared difference between observed and predicted data points. The RMSE has the same unit as the target feature and is generally considered the model error. A lower RMSE value represents superior prediction results. The formula of the RMSE is provided by(7)RMSE=∑j=1nRj−Rpredicted,j2n,where n is the number of observations, Rj denotes the empirical (simulated) network robustness, and Rpredicted,j is the predicted value of robustness for the observation j.R2 is used to represent the general prediction performance of regression models. R2 is one minus the ratio of the remaining variance and the original variance. The formula of R2 is provided by(8)R2=1−∑j=1nRj−Rpredicted,j2∑j=1nRj−R¯j2,where n is the number of observations, Rj is the simulation robustness, Rpredicted,j denotes the predicted value for observation j, and R¯j is the average of all the simulation robustness. R2 varies between 0 (the model has no prediction ability) and 1 (the model correctly predicts all values).The residual error,ε=Rempirical−Rpredicted, is simply an error between the empirical (simulated) network robustness and the predicted value of robustness. The distribution histogram of ε is expected to be close to the origin. Furthermore, the most important assumption of a linear regression model is that residual errors are independent, and consequently, these errors are expected to be normally distributed.The network is analyzed using the “graph-tool” library inPython. All data preparation, model building, and evaluation are written using the Python code. The hardware for numerical simulations is a PC with an i9-10850 Intel processor and 32 GB RAM.


## 3.1. Simple Linear Regression Model (SLR)

Linear regression is the simplest model for prediction. The SLR model between the network robustnessR and an NSI x is expressed by the linear equation:(4)R=a0+a1x,where a0 is the intercept and a1 is the slope. In (4), an ordinary least square (OLS) is applied for estimating coefficients by minimizing an appropriate loss function [45, 46]. Once the OLS process, which is also called the fitting process, is performed, we can use (1) to predict the robustness R of a new network for a given indicator x. In addition, we derive a statistics t-test from the OLS process with the null hypothesis H0: a1 = 0. A rejection of H0 means that there is a significant linear relationship between R and the NSI x.We run the SLR model fit for all NSIs listed in Table1 excluding E because it can be expressed in terms of two other NSIs : E = N < k>/2.


## 3.2. Multiple Linear Regression Model

Multiple linear regression (MLR) is an extension of SLR for multidimension variablesx = (x1, x2, …, xn), where x1, x2, …, xn are NSIs. The linear equation between network robustness R and NSIs is as follows:(5)R=a0+a1x1+a2x2+⋯+anxn,where ai are coefficients obtained from the OLS method.


## 3.3. Random Forest Model

The random forest (RF) belongs to the ensemble class of ML models, indicating that it aggregates the prediction from an ensemble of ML base models, here, decision tree regression (DTR) models. We briefly describe the DTR in the following section.A DTR starts with the root of the tree containing all samples (48 networks in our case). It then splits into two different nodes by selecting samples whose value of a certain variable is higher or lower than a certain threshold value. Figure2(a) represents a basic decision tree diagram for our dataset. The root node containing 48 networks splits into two other nodes by considering whether the variable (NSI in our case) scale-free exponent α is higher or lower than 2.5.Figure 2
(a) An example of a decision tree: the root node containing 48 networks splits into two other nodes, Node 11 and Node 12, with 13 and 35 networks, respectively, according to the value of the scale-free exponentα. Then, Node 12 splits into two other nodes, Node 21 and Node 22, with 15 and 20 networks, respectively, according to the value of the network density <k>. We assume that at Node 11, Node 21, and Node 22, no split is possible because of a certain stopping rule, and thus, they become final leaves. In general, any NSI can be used to divide networks at any split, and the decision tree can be arbitrarily complex depending on the stopping rule. (b) An illustration of the same decision tree in the 2-dimension (α and <k>) space with final leaves.
(a)(b)The DTR selects the variable, and its splitting value is based on information theory, in concrete considering the entropy concept. Entropy is a metric of uncertainty of a node. The DTR splits a node by maximizing the information gain, which is the weighted difference between the total entropy of two resulting nodes and the entropy of the initial node. The DTR successively splits until a stopping condition is reached, for example if the size of the current node is smaller than 20. The final node is also called a leaf node. In Figure2(a), after the first split of the root, the left child node becomes a leaf node, while the right child node continues to split into two leaf nodes.Once the final DTR is obtained, it can be used to predict the value of a new sample as follows. The new sample will be classified into one of the leaves, and its prediction value will be the average value of all the samples that are classified into the same leaf.Finally, the RF model creates multiple decision trees randomly drawn from the data, usually several hundred, and averaging the results from all trees to output a new result often leads to strong predictions [47, 48].The decision tree can fit nonlinear datasets because it can split the same NSI multiple times. However, decision tree is easy to be overfitting, i.e., it is too sensitive to the training data while failing to predict new coming (testing) data. In order to address this problem, a random forest (RF) model is obtained by creating multiple randomly drawn decision trees from data, usually several hundred. The final regression prediction will be the average prediction of all the decision trees [47–49] (in this work, we implement an RF with 300 DTRs). Using an RF, “feature importance” measurement can be derived to rank the NSI [50].


## 3.4. Data Preparation, Validation, and Performance Evaluation

All NSIs can be computed from the network’s data, and thus, our dataset did not contain missing values. We also excludeE because of redundancy as mentioned above. The other 8 NSIs are normalized to avoid large differences in the indicators’ range:(6)xi,j′=xi,j−x¯iσxi,where xi,j is the value of the NSI i for observation (network) j and x¯i and σxi are the mean and the standard deviation of the NSI i, respectively.In the first step, we use the whole dataset to build ML models and compare the results between models and two target variables. However, due to overfitting problems in many ML models, the model’s performance for new data is not always coherent as that in the training step, and we need to validate models in the second step. We choose the leave-one-out validation [51]. In this way, we train each of the above models 48 times: each time the whole dataset excluding one observation is used to train the model, and then, the model is used to predict the target value of the remaining (hold-out) observations and repeats for each of 48 hold-out observations. The overall evaluation result is the average across all 48 regressions.It is noted that for the SLR model, we only consider regression coefficients in order to analyze the dependence of robustness metrics with respect to each NSI. However, for MLR and RF models, we analyze the prediction of robustness metrics using four common evaluation metrics for regression problems, the root mean square error (RMSE) and the coefficient of determination (also named the explained variance ratio,R2) as analytical metrics and the frequency distribution and the Q-Q plot of residual errors as graphical metrics.RMSE is the square root of the summation of the squared difference between observed and predicted data points. The RMSE has the same unit as the target feature and is generally considered the model error. A lower RMSE value represents superior prediction results. The formula of the RMSE is provided by(7)RMSE=∑j=1nRj−Rpredicted,j2n,where n is the number of observations, Rj denotes the empirical (simulated) network robustness, and Rpredicted,j is the predicted value of robustness for the observation j.R2 is used to represent the general prediction performance of regression models. R2 is one minus the ratio of the remaining variance and the original variance. The formula of R2 is provided by(8)R2=1−∑j=1nRj−Rpredicted,j2∑j=1nRj−R¯j2,where n is the number of observations, Rj is the simulation robustness, Rpredicted,j denotes the predicted value for observation j, and R¯j is the average of all the simulation robustness. R2 varies between 0 (the model has no prediction ability) and 1 (the model correctly predicts all values).The residual error,ε=Rempirical−Rpredicted, is simply an error between the empirical (simulated) network robustness and the predicted value of robustness. The distribution histogram of ε is expected to be close to the origin. Furthermore, the most important assumption of a linear regression model is that residual errors are independent, and consequently, these errors are expected to be normally distributed.The network is analyzed using the “graph-tool” library inPython. All data preparation, model building, and evaluation are written using the Python code. The hardware for numerical simulations is a PC with an i9-10850 Intel processor and 32 GB RAM.


## 4. Results

### 4.1. Network Robustness as a Function of the NSIs and SLR T-Test

The simulation robustness of each network RIB and RRD is represented in Table2. Overall, we found that RRD is slightly smaller than RIB for most networks (43 out of 48 networks), with an average of 0.148 vs. 0.173, respectively. It suggests that the RD strategy has more efficacy than IB for attacking real-world social networks. The largest and sparsest network, Email-EuAll (N = 265,216 and <k ≥ 1.58), has the smallest robustness with an equal RIB and RRD of 0.001. In contrast, the gemsec_deezer_HR network, with N = 54,575 and <k ≥ 9.12, has the strongest robustness with an RIB and RRD of 0.375 and 0.338, respectively.Table 2
Simulation result by IB and RD node attack strategies, represented by the network robustness metricsRIB and RRD, for all 48 real-world social networks (sort by networks’ size from smallest to largest).
Short namesNERIBRRDmusae_PTBR1,91431,3000.2570.214musae_chameleon2,27936,1020.1530.143Hamsterster2,42616,6300.1340.133Tvshow3,89417,2630.1390.153musae_RU4,38737,3050.2090.149musae_ES4,65059,3830.2480.202musae_squirrel5,203217,0740.2980.184CA-GrQc5,24428,9810.0570.069Politician5,91041,7300.1980.195musae_FR6,551112,6670.2880.240Advogato6,55151,3320.1000.090Government7,05989,4560.3110.283Wiki-vote7,117103,6900.1360.144musae_ENGB7,12835,3250.1800.132lastfm_asia7,62627,8070.1710.137musae_DE9,500153,1390.2820.229CA-HepTh9,87951,9720.0970.091BlogCatalog310,312333,9830.1940.181public_figure11,56767,1150.2040.168musae_crocodile11,633180,0210.1240.071CA-HepPh12,010237,0110.1380.162Anybeat12,64567,0530.0390.028Athletes13,86886,8590.2340.199Company14,11552,3110.1750.150CA-AstroPh18,774396,1610.1930.212musae_facebook22,472171,0030.2280.206CA-CondMat23,135186,9370.1130.113Soc-gplus23,62839,2420.0020.001Cit-HepTh27,772352,8080.3420.307new_sites27,919206,2600.2640.228deezer_Europe28,28392,7530.1860.153Cit-HepPh34,548421,5790.3500.307Email-Enron36,694367,6630.0480.039musae_git37,702289,0040.1680.122deezer_RO41,775125,8270.2610.200deezer_HU47,540222,8880.3430.287Artists50,515819,3060.2990.265deezer_HR54,575498,2030.3750.338Brightkite58,228214,0780.1070.083TheMarker69,4131,644,8490.1130.100Soc-Epinions175,881508,8380.0660.054Slashdot081177,362905,4690.0930.073Slashdot090282,170948,4650.1030.077BlogCatalog188,7844,186,3900.0720.063BlogCatalog297,8842,043,7010.0160.014Douban154,908654,1880.0260.024Gowalla196,591950,3270.1600.115Email-EuAll265,216420,0460.0010.001Average38,026391,6980.1730.148Std51,490687,6010.0980.085In Figure3, we plot RRD and RIB as a function of 8 independent NSIs, and we found that RRD and RIB behave similarly in all cases. The SLR unveils some significant relationships between R and NSIs (Figure 3 and Table 3). For example, in Figure 3(a), we can see that both RRD and RIB slightly decrease with the network size N. This linear dependence between robustness RRD and RIB and N is tested by using the SLR model, and we found that it is statistically significant, with a confidence level of 95% (p value <0.05, Table 3).Figure 3
Simulation result by IB and RD node attack strategies, represented by the network robustness metricsRIB and RRD, for all the 48 real-world social networks as a function of 8 NSIs.
(a)(b)(c)(d)(e)(f)(g)(h)Table 3
The SLR results for 8 NSIs. The last two columns show the slope, and in parenthesis, theR2 values of the SLR between the NSI and RIB or RRD. The bold character with an asterisk indicates a significant relationship, with a confidence level of 95%.
NbNSIRIBRRD1N−6.920·10−7(0.132)∗−6.377·10−7(0.150)∗2<k>0.0006 (0.015)0.0004 (0.010)3α0.0215 (0.031)0.0247 (0.056)4α2−0.0039 (0.007)−0.0011 (0.000)5α−0.3282 (0.019)−0.1184 (0.003)6Q0.0917 (0052)0.1022 (0.087)∗7C0.0274 (0.001)0.0781 (0.021)8Cl−0.1515 (0.010)−0.1607 (0.016)Interestingly, RRD and RIB do not statistically linearly depend on the network density <k> as found previously in [4, 52] (Figure 3(b) and Table 3). This contrasting observation would suggest that network robustness also depends on other NSIs and that the network density alone cannot predict the whole network’s robustness as previously seen.BesidesN, the only other NSI that shows a significant linear relationship is the modularity Q (Figure 3(f)) in the case of RRD.However, in Figure3, we still observe some nonlinear dependencies. For example, in Figure 3(e), we show that network robustness decreases with the assortativity coefficient a when a > 0. However, it decreases faster when a is close to 0 and increases with a when a < 0.Similarly, in Figure 3(g), we found that the relationship between RRD and RIB and the global clustering coefficient C follows an inverted u-shaped pattern. We ran a two-line statistical test [53] and found that two-line (or broken line) regression is significantly better than a single-line test. The breakpoint was found to be C = 0.115. Both RRD and RIB linearly increase with C (with a significance level of 95%) up to the breakpoint and linearly decrease with C (with a significance level of 95%). One possible explanation is that if the network is sparse, more triplets help increase the network’s connectivity and thus increase its robustness. However, above a certain value (when C = 0.115), more triplets may denote the presence of hubs or central nodes, which are likely to be the target of intentional node removal strategies such as RD and IB, consequently lowering network robustness.


### 4.2. Machine Learning Prediction of Network Robustness

The results of the previous section suggest that the social network’s robustness depends on multiple NSIs in a highly complex, multidimensional, and nonlinear manner. To improve the model prediction, in this section, we use two multiple variable ML models, MLR and RF, to predict network robustness.The results of multiple linear regression MLR are shown in Table4. We found that both RIB and RRD have a positive overall linear regression coefficient with respect to α, Q, Cl, and <k> and a negative overall linear regression coefficient with respect to α2, a, C, and N. Moreover, the MLR result indicate that α, α2, and <k> are the most significant coefficients. A positive linear regression coefficient for the average node degree <k> suggests that networks are more robust when k is higher, while all other NSIs are fixed. This result agrees with previous outcomes demonstrating that denser networks may be more resistant to the attack [4, 52]. However, the different results between the MLR and SLR would suggest that there is a strong correlation between <k> and other NSIs. In addition, the MLR model predicts RIB better than RRD, with an R2 coefficient of 58.04% compared to 51.76%. Nevertheless, the RMSE was smaller for RRD, with a value of 0.0657, compared to 0.0709 for RIB (this is because the standard deviation of RIB is higher than that of RRD, as shown in Table 2 (bottom row)).Table 4
Fit coefficients and the evaluation result given by the MLR.RIB or RRD columns show the slope coefficient, and in parenthesis, the standard error values for the NSI. The bold character with an asterisk indicates a significant relationship between the NSI and the robustness R, with a confidence level of 95%.
NbNSIRegression coefficientsRIBRRD1α0.113 (0.028)∗0.088 (0.026)∗2α2−0.118 (0.028)∗−0.083 (0.026)∗3α−0.029 (0.013)∗−0.025 (0.012)4Q0.047 (0.02)∗0.038 (0.019)5C−0.034 (0.016)∗−0.016 (0.015)6Cl0.005 (0.014)0.007 (0.013)7N−0.013 (0.013)−0.014 (0.012)8<k>0.077 (0.017)∗0.056 (0.016)∗9Intercept0.173 (0.01)∗0.148 (0.009)∗MLR resultsRMSE0.07090.0657R258.04%51.76%Because of the nonlinearity found in the previous section, we expect that the regression result using the RF model will be improved. Table5 represents the regression result of the RF model. We found that R2 increases to 92.24% and 91.88% for RIB and RRD regressions, respectively. Interestingly, the RF model predicts RRD roughly as well as RRD, while MLR predicts RIB better than RRD, suggesting that RRD may follow a stronger nonlinear relationship with NSIs than RIB. Additionally, the RMSE improved both for RIB and RRD, with a value of 0.0272 and 0.0241, respectively. Interestingly, the feature importance ranking in Table 5 shows that with an RF model, the assortativity a, the global closeness C, and the node number N are the most important NSIs. This result agrees with the exploratory observations shown in Figure 3 as discussed above.Table 5
Feature importance of the NSI and the evaluation result given by RF.
NSIFeature importanceRIBRRDα0.06220.0654α20.05350.0463a0.27650.1912Q0.08230.0658C0.11140.1834Cl0.05810.0584N0.26830.2759<k>0.08730.1133RMSE0.02720.0241R292.24%91.88%In Figure4, we compare network robustness RIB and RRD with the prediction value given by MLR and RF using a scatter plot. The scatter plots indicate that RF fit data significantly better than MLR, where the predicted actual data points are closer to the diagonal line y = x. Meanwhile, for MLR regression, we still found nonlinear dependency between the actual and predicted values. As a matter of fact, the MLR model was not able to capture the inherent nonlinearity dependency in the actual data. We also analyzed the residual errors of the above regression using the frequency histogram and QQ-plot and found that they follow a normal distribution relatively well (Figures 5–8).Figure 4
Scatter plots between the predicted value of robustness (R predicted) and simulated (R empirical) for MLR (a) and RF model (b). The model is trained using the whole dataset, and the predicted values are of the same dataset.
(a)(b)Figure 5
Histogram of residual errors for MLR prediction of the IB strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 6
Histogram of residual errors for MLR prediction of the RD strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 7
Histogram of residual errors for RF prediction of the IB strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 8
Histogram of residual errors for RF prediction of the RD strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Finally, we run leave-one-out regression for both models MLR and RF in order to avoid overfitting. The result is summarized in Table6, and the scatter plots are shown in Figure 9. We found that the prediction result is less accurate than the above “in-sample” training with lower RMSEs in both MLR and RF models. We obtained an RMSE of 0.0812 and 0.0760 for RIB and RRD predictions using MLR, respectively, and an RMSE of 0.0733 and 0.0636 for RIB and RRD predictions using RF, respectively. Even though the regression results are less effective because we predict the single sample which is independent of the remaining samples used for training (building the ML model), residual errors still fit well to a normal distribution as shown in the histogram and QQ-plots (Figures 10–13).Table 6
MLR and RF evaluation results using the leave-one-out method.
MLRRFRIBRMSE0.08120.0733R231.30%43.87%RRDRMSE0.07600.0636R219.30%43.47%Figure 9
Scatter plots between the predicted value of robustness (R predicted) and simulated (R empirical) of the hold-out observation for MLR (a) and RF model (b). The model is trained using the whole dataset excluding one observation (hold-out observation) and is used to predict the outcome of the hold-out observation.
(a)(b)Figure 10
Histogram of residual errors for MLR prediction of the IB strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 11
Histogram of residual errors for MLR prediction of the RD strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 12
Histogram of residual errors for RF prediction of the IB strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 13
Histogram of residual errors for RF prediction of the RD strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)


## 4.1. Network Robustness as a Function of the NSIs and SLR T-Test

The simulation robustness of each network RIB and RRD is represented in Table2. Overall, we found that RRD is slightly smaller than RIB for most networks (43 out of 48 networks), with an average of 0.148 vs. 0.173, respectively. It suggests that the RD strategy has more efficacy than IB for attacking real-world social networks. The largest and sparsest network, Email-EuAll (N = 265,216 and <k ≥ 1.58), has the smallest robustness with an equal RIB and RRD of 0.001. In contrast, the gemsec_deezer_HR network, with N = 54,575 and <k ≥ 9.12, has the strongest robustness with an RIB and RRD of 0.375 and 0.338, respectively.Table 2
Simulation result by IB and RD node attack strategies, represented by the network robustness metricsRIB and RRD, for all 48 real-world social networks (sort by networks’ size from smallest to largest).
Short namesNERIBRRDmusae_PTBR1,91431,3000.2570.214musae_chameleon2,27936,1020.1530.143Hamsterster2,42616,6300.1340.133Tvshow3,89417,2630.1390.153musae_RU4,38737,3050.2090.149musae_ES4,65059,3830.2480.202musae_squirrel5,203217,0740.2980.184CA-GrQc5,24428,9810.0570.069Politician5,91041,7300.1980.195musae_FR6,551112,6670.2880.240Advogato6,55151,3320.1000.090Government7,05989,4560.3110.283Wiki-vote7,117103,6900.1360.144musae_ENGB7,12835,3250.1800.132lastfm_asia7,62627,8070.1710.137musae_DE9,500153,1390.2820.229CA-HepTh9,87951,9720.0970.091BlogCatalog310,312333,9830.1940.181public_figure11,56767,1150.2040.168musae_crocodile11,633180,0210.1240.071CA-HepPh12,010237,0110.1380.162Anybeat12,64567,0530.0390.028Athletes13,86886,8590.2340.199Company14,11552,3110.1750.150CA-AstroPh18,774396,1610.1930.212musae_facebook22,472171,0030.2280.206CA-CondMat23,135186,9370.1130.113Soc-gplus23,62839,2420.0020.001Cit-HepTh27,772352,8080.3420.307new_sites27,919206,2600.2640.228deezer_Europe28,28392,7530.1860.153Cit-HepPh34,548421,5790.3500.307Email-Enron36,694367,6630.0480.039musae_git37,702289,0040.1680.122deezer_RO41,775125,8270.2610.200deezer_HU47,540222,8880.3430.287Artists50,515819,3060.2990.265deezer_HR54,575498,2030.3750.338Brightkite58,228214,0780.1070.083TheMarker69,4131,644,8490.1130.100Soc-Epinions175,881508,8380.0660.054Slashdot081177,362905,4690.0930.073Slashdot090282,170948,4650.1030.077BlogCatalog188,7844,186,3900.0720.063BlogCatalog297,8842,043,7010.0160.014Douban154,908654,1880.0260.024Gowalla196,591950,3270.1600.115Email-EuAll265,216420,0460.0010.001Average38,026391,6980.1730.148Std51,490687,6010.0980.085In Figure3, we plot RRD and RIB as a function of 8 independent NSIs, and we found that RRD and RIB behave similarly in all cases. The SLR unveils some significant relationships between R and NSIs (Figure 3 and Table 3). For example, in Figure 3(a), we can see that both RRD and RIB slightly decrease with the network size N. This linear dependence between robustness RRD and RIB and N is tested by using the SLR model, and we found that it is statistically significant, with a confidence level of 95% (p value <0.05, Table 3).Figure 3
Simulation result by IB and RD node attack strategies, represented by the network robustness metricsRIB and RRD, for all the 48 real-world social networks as a function of 8 NSIs.
(a)(b)(c)(d)(e)(f)(g)(h)Table 3
The SLR results for 8 NSIs. The last two columns show the slope, and in parenthesis, theR2 values of the SLR between the NSI and RIB or RRD. The bold character with an asterisk indicates a significant relationship, with a confidence level of 95%.
NbNSIRIBRRD1N−6.920·10−7(0.132)∗−6.377·10−7(0.150)∗2<k>0.0006 (0.015)0.0004 (0.010)3α0.0215 (0.031)0.0247 (0.056)4α2−0.0039 (0.007)−0.0011 (0.000)5α−0.3282 (0.019)−0.1184 (0.003)6Q0.0917 (0052)0.1022 (0.087)∗7C0.0274 (0.001)0.0781 (0.021)8Cl−0.1515 (0.010)−0.1607 (0.016)Interestingly, RRD and RIB do not statistically linearly depend on the network density <k> as found previously in [4, 52] (Figure 3(b) and Table 3). This contrasting observation would suggest that network robustness also depends on other NSIs and that the network density alone cannot predict the whole network’s robustness as previously seen.BesidesN, the only other NSI that shows a significant linear relationship is the modularity Q (Figure 3(f)) in the case of RRD.However, in Figure3, we still observe some nonlinear dependencies. For example, in Figure 3(e), we show that network robustness decreases with the assortativity coefficient a when a > 0. However, it decreases faster when a is close to 0 and increases with a when a < 0.Similarly, in Figure 3(g), we found that the relationship between RRD and RIB and the global clustering coefficient C follows an inverted u-shaped pattern. We ran a two-line statistical test [53] and found that two-line (or broken line) regression is significantly better than a single-line test. The breakpoint was found to be C = 0.115. Both RRD and RIB linearly increase with C (with a significance level of 95%) up to the breakpoint and linearly decrease with C (with a significance level of 95%). One possible explanation is that if the network is sparse, more triplets help increase the network’s connectivity and thus increase its robustness. However, above a certain value (when C = 0.115), more triplets may denote the presence of hubs or central nodes, which are likely to be the target of intentional node removal strategies such as RD and IB, consequently lowering network robustness.


## 4.2. Machine Learning Prediction of Network Robustness

The results of the previous section suggest that the social network’s robustness depends on multiple NSIs in a highly complex, multidimensional, and nonlinear manner. To improve the model prediction, in this section, we use two multiple variable ML models, MLR and RF, to predict network robustness.The results of multiple linear regression MLR are shown in Table4. We found that both RIB and RRD have a positive overall linear regression coefficient with respect to α, Q, Cl, and <k> and a negative overall linear regression coefficient with respect to α2, a, C, and N. Moreover, the MLR result indicate that α, α2, and <k> are the most significant coefficients. A positive linear regression coefficient for the average node degree <k> suggests that networks are more robust when k is higher, while all other NSIs are fixed. This result agrees with previous outcomes demonstrating that denser networks may be more resistant to the attack [4, 52]. However, the different results between the MLR and SLR would suggest that there is a strong correlation between <k> and other NSIs. In addition, the MLR model predicts RIB better than RRD, with an R2 coefficient of 58.04% compared to 51.76%. Nevertheless, the RMSE was smaller for RRD, with a value of 0.0657, compared to 0.0709 for RIB (this is because the standard deviation of RIB is higher than that of RRD, as shown in Table 2 (bottom row)).Table 4
Fit coefficients and the evaluation result given by the MLR.RIB or RRD columns show the slope coefficient, and in parenthesis, the standard error values for the NSI. The bold character with an asterisk indicates a significant relationship between the NSI and the robustness R, with a confidence level of 95%.
NbNSIRegression coefficientsRIBRRD1α0.113 (0.028)∗0.088 (0.026)∗2α2−0.118 (0.028)∗−0.083 (0.026)∗3α−0.029 (0.013)∗−0.025 (0.012)4Q0.047 (0.02)∗0.038 (0.019)5C−0.034 (0.016)∗−0.016 (0.015)6Cl0.005 (0.014)0.007 (0.013)7N−0.013 (0.013)−0.014 (0.012)8<k>0.077 (0.017)∗0.056 (0.016)∗9Intercept0.173 (0.01)∗0.148 (0.009)∗MLR resultsRMSE0.07090.0657R258.04%51.76%Because of the nonlinearity found in the previous section, we expect that the regression result using the RF model will be improved. Table5 represents the regression result of the RF model. We found that R2 increases to 92.24% and 91.88% for RIB and RRD regressions, respectively. Interestingly, the RF model predicts RRD roughly as well as RRD, while MLR predicts RIB better than RRD, suggesting that RRD may follow a stronger nonlinear relationship with NSIs than RIB. Additionally, the RMSE improved both for RIB and RRD, with a value of 0.0272 and 0.0241, respectively. Interestingly, the feature importance ranking in Table 5 shows that with an RF model, the assortativity a, the global closeness C, and the node number N are the most important NSIs. This result agrees with the exploratory observations shown in Figure 3 as discussed above.Table 5
Feature importance of the NSI and the evaluation result given by RF.
NSIFeature importanceRIBRRDα0.06220.0654α20.05350.0463a0.27650.1912Q0.08230.0658C0.11140.1834Cl0.05810.0584N0.26830.2759<k>0.08730.1133RMSE0.02720.0241R292.24%91.88%In Figure4, we compare network robustness RIB and RRD with the prediction value given by MLR and RF using a scatter plot. The scatter plots indicate that RF fit data significantly better than MLR, where the predicted actual data points are closer to the diagonal line y = x. Meanwhile, for MLR regression, we still found nonlinear dependency between the actual and predicted values. As a matter of fact, the MLR model was not able to capture the inherent nonlinearity dependency in the actual data. We also analyzed the residual errors of the above regression using the frequency histogram and QQ-plot and found that they follow a normal distribution relatively well (Figures 5–8).Figure 4
Scatter plots between the predicted value of robustness (R predicted) and simulated (R empirical) for MLR (a) and RF model (b). The model is trained using the whole dataset, and the predicted values are of the same dataset.
(a)(b)Figure 5
Histogram of residual errors for MLR prediction of the IB strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 6
Histogram of residual errors for MLR prediction of the RD strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 7
Histogram of residual errors for RF prediction of the IB strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Figure 8
Histogram of residual errors for RF prediction of the RD strategy for the whole dataset (a) and its QQ-plot (b).
(a)(b)Finally, we run leave-one-out regression for both models MLR and RF in order to avoid overfitting. The result is summarized in Table6, and the scatter plots are shown in Figure 9. We found that the prediction result is less accurate than the above “in-sample” training with lower RMSEs in both MLR and RF models. We obtained an RMSE of 0.0812 and 0.0760 for RIB and RRD predictions using MLR, respectively, and an RMSE of 0.0733 and 0.0636 for RIB and RRD predictions using RF, respectively. Even though the regression results are less effective because we predict the single sample which is independent of the remaining samples used for training (building the ML model), residual errors still fit well to a normal distribution as shown in the histogram and QQ-plots (Figures 10–13).Table 6
MLR and RF evaluation results using the leave-one-out method.
MLRRFRIBRMSE0.08120.0733R231.30%43.87%RRDRMSE0.07600.0636R219.30%43.47%Figure 9
Scatter plots between the predicted value of robustness (R predicted) and simulated (R empirical) of the hold-out observation for MLR (a) and RF model (b). The model is trained using the whole dataset excluding one observation (hold-out observation) and is used to predict the outcome of the hold-out observation.
(a)(b)Figure 10
Histogram of residual errors for MLR prediction of the IB strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 11
Histogram of residual errors for MLR prediction of the RD strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 12
Histogram of residual errors for RF prediction of the IB strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)Figure 13
Histogram of residual errors for RF prediction of the RD strategy for the leave-one-out sample (a) and its QQ-plot (b).
(a)(b)


## 5. Discussion and Conclusion

In this work, we have analyzed the robustness of 48 real-world social networks with the node number ranging over five orders of magnitude, from 1,914 to 265,216. Using Monte Carlo simulations, we have run two commonly used node attack strategies, IB and RD strategies, whose computation time is within our hardware capability. We found that their corresponding simulation time,tIB and tRD, scales linearly with the product of the network’s node number and edge number, i.e., N × E. We also found that the two attack strategies IB and RD present similar efficacy when evaluated by the unique robustness metric R, with RD slightly better than IB (average RRD is slightly smaller than average RIB). It suggests that for the social networks used in this study, the RD strategy is the most efficient strategy to dismantle (breakdown) networks, both in terms of computational cost and breakdown efficiency.To understand how the structure of a social network determines its robustness, we investigate the relationship between the metricR and a set of network structural indicators (NSIs) from the literature. The simple linear regression (SLR) between R and NSIs shows low goodness of fitting, and it is overall not able to produce significant prediction models. The low goodness of SLR would indicate that network robustness depends on NSIs in a nonlinear manner.To improve fitting, we have developed two machine learning models to predict two robustness metricsRRD and RRD from the combination of 8 NSIs, multiple linear regression (MLR), and random forest (RF) model. The latter one is chosen as it can handle nonlinear data well and is built on a collection of base models, decision tree classifiers. We found clearly that the random forest model can predict network robustness better than the multiple linear regression model. In concrete, the RF model predicts network robustness with an RMSE of 0.0272 and 0.0241 for RIB and RRD, respectively. This result is encouraging to predict real-world social network robustness, although the error is about 16% (for RIB, the RMSE is 0.0272 compared to an average RIB of 0.173, and for RRD, the RMSE is of 0.0241 compared to an average RRD of 0.148). Meanwhile, when the leave-one-out evaluation is applied, the RMSE increases to 0.0733 and 0.0636 for RIB and RRD, respectively, which is about one-third of the average value.Finally, MLR indicates that the most important factors to predict RIB are the exponentα and the average node degree <k>, for both RIB and RRD. In particular, a higher value of α is correlated with higher RIB and RRD. Higher absolute values of the exponent α denote a network with fewer hub nodes (highly connected nodes) [35]. In consequence, the RD and IB attack strategies cannot find large hub nodes whose removal may disintegrate the network faster, resulting in higher values of RRD and RIB. Additionally, MLR indicates that <k> is positively related to lower RIB and RIB. This last outcome agrees with previous results, demonstrating that networks with higher edge density may be more resistant to the attack [4, 52]. On the other hand, it confirms that SLR, which focuses on a single NSI, may not be able to predict the robustness of real-world social networks.Our work demonstrates that the ML model can be used to predict network robustness with acceptable results. Therefore, it alleviates the need to run a full Monte Carlo simulation on a network when only approximate robustness is needed. Meanwhile, more network datasets are expected to improve the accuracy of ML models. This work also contributes to the understanding of the relationship between real-world social network robustness and its structural indicators. Finally, we have proved that using a data-driven approach to predict the outcome of the nonlinear and complex dynamic process, such as network robustness, is an appropriate approach [54–60].



---

*Source: 3616163-2022-11-09.xml*