Social network analysis (SNA) provides information about social and individual relationships by graphically and mathematically monitoring global structures and local entities. Network surveillance applies statistical process monitoring (SPM) to a network and aims to quickly detect network anomalies. The network is monitored using control charts to detect anomalous behavior in each period of the network data. Therefore, network surveillance can help prevent conflicts and crises in social situations by identifying global and local perspectives. Many studies have addressed network-surveillance schemes. For example, Hosseini and Noorossana (2018) compared the performance of detecting outbreaks by applying the average and standard deviation of degree measures of a network to exponentially weighted moving average (EWMA) and cumulative sum (CUSUM) charts. Wilson et al. (2019) applied a degree corrected stochastic block model (DCSBM) to Shewhart charts to detect local and global changes. Yu et al. (2018) proposed a multivariate procedure to monitor an individual’s propensity by using the Hotelling T² chart. Moreover, Yu et al. (2021) compared several monitoring methods using the global network summary statistics, the scan-based method proposed by Preibe et al. (2005), and the model-based methods proposed by Yu et al. (2018) and Wilson et al. (2019).

Networks comprise nodes (vertices) and edges (links), where nodes represent actors or entities and edges represent communication between nodes. Networks can be divided into unweighted or weighted networks according to the types of edges. Edges in unweighted networks take a value of 0 or 1 depending on whether two nodes are communicating or not. Edges in weighted networks take non-negative values such as the number of communications between two nodes. Additionally, networks can be divided into two main categories: directed and undirected networks depending on whether the network is directional or not. An undirected network does not consider the direction of communication between two nodes. For example, given nodes i and j for i ≠ j, communication between nodes i and j is the same as communication between nodes j and i. Otherwise, it is a directed network, or digraph. A network graph can be represented by an adjacency matrix that illustrates the edges between nodes. Network data can be analyzed more easily by mathematically representing the networks using adjacency matrices.

Centrality measures indicate which node is most important in the network. Freeman (1977, 1978) proposed degree, closeness, and betweenness centrality measures in unweighted networks. Degree centrality is the number of edges directly connected to a node and is representative of the node’s popularity and communication activity. Scott (1991) argued that degree centrality can be regarded as local centrality. However, closeness and betweenness centralities are considered measures of global centrality in terms of the distance among various nodes. Closeness and betweenness centralities are associated with the number of nodes that lie within the shortest distance from all other nodes in the network, helping clarify the global network structure. Brandes (2001), Newman (2001), and Barrat et al. (2004) generalized these measures and applied them to weighted networks. Brandes (2001) and Newman (2001) considered the shortest path algorithm proposed by Dijkstra (1959) under the assumption that the most critical actor or entity is on the shortest path and can easily access all nodes. Opsahl et al. (2010) proposed a generalized form that combines the number of edges and their weights in order to consider both measures in a weighted network. Abassi et al. (2011) discussed the relationship between scholar’s performance and SNA measures using normalized centrality measures. Abassi et al. (2013) also proposed hybrid centrality measures that combine existing centrality measures to improve the importance of nodes, and applied them to a co-author network to evaluate the proposed measures.

Because centrality measures in weighted networks are continuous variables, previous studies on SNA have generally used continuous statistics to evaluate performance through control charts. However, if several centrality measures are transformed into one categorical variable through classification, only a single chart can be used to monitor social networks more effectively. By using this method, the problem for monitoring social networks using centrality measures turns into that of monitoring categorical processes. Recently, Perry (2020) classified the observed networks over time into two categories based on the average values of transitivity and reciprocity measures, and applied them to an EWMA chart to monitor the hierarchical tendency. Furthermore, he compared the out-of-control average run length (ARL) performance of the proposed EWMA chart with that of the multinomial CUSUM chart proposed by Ryan et al. (2011).

A brief explanation of the multinomial CUSUM chart proposed by Ryan et al. (2011) is as follows: They proposed the multinomial CUSUM chart for monitoring in situations where items were classified into more than two categories, and they compared with multiple Bernoulli CUSUM charts. The multinomial CUSUM chart is useful when monitoring more than two categories with specified direction of out-of-control shifts, and unlike other charts which monitor categorical data, this chart does not require aggregation of items into samples.

In this paper, we propose a procedure for creating a categorical variable having four categories by classifying degree and closeness centrality measures according to their average values in weighted networks, and then monitoring this variable using the multinomial CUSUM chart. By applying the four categories to the multinomial CUSUM chart, we can simultaneously monitor both local and global views of the network. We also compare the performance of the proposed procedure with that of the EWMA charts using degree centrality and closeness centrality individually.

The next sections are as follows: In Section 2, we define degree and closeness centrality measures, and in Section 3, we describe the control charts used in the simulations. In Section 4, we propose a procedure for monitoring one categorical variable transformed from two centrality measures, and in Section 5, we describe the simulation settings and discuss the simulation results. Finally, we provide our conclusions in Section 6.

2.1. Degree centrality

Degree centrality indicates the node’s communication activity and popularity. It has the advantage of being uncomplicated and easy to calculate. Degree is a local centrality measure because it is calculated based on the number of neighbors of a focal node. Freeman (1977, 1978) defined degree centrality as the number of directly connected nodes in a binary network. The degree centrality for node i in unweighted networks is defined as

where x_{i j} is a binary value of 1 when nodes i and j interact with each other and 0 otherwise, and N is the total number of nodes.

However, since this definition does not take into account the weights representing the frequency of communications or the closeness between nodes, the use of this measure in weighted networks can lead to significant information loss. Barrat et al. (2004) proposed the degree centrality for node i in weighted networks as in Equation (2.1) considering weights.

where w_{i j} denotes the weight between nodes i and j.

2.2. Closeness centrality

Closeness centrality is the inverse of the shortest path between nodes, indicating that an efficient node is close to all the nodes. This centrality measure is related to global centrality. For example, a node may have a high degree centrality but a low value of closeness centrality in the network because the node is popular locally but not globally. There has been great interest in defining the shortest path between nodes. It assumes that the higher the number of intermediate nodes, the higher the communication cost. For example, a node with many intermediary nodes takes more time to acquire information, which distorts and delays the communication between nodes.

Freeman (1977, 1978) proposed the closeness centrality for node i in unweighted networks defined as

where d(i, j) is the shortest distance between nodes i and j and is defined as

for intermediary nodes g on paths between node i and j.

However, this measure has the disadvantage of losing a lot of the information contained in weighted networks. Newman (2001) considered the relationship between the weight and distance by using Dijkstra (1959)’s algorithm. The closeness centrality for node i in weighted networks proposed by Newman (2001) is given by

where d_w(i, j) is the shortest distance used Dijkstra’s algorithm and is defined as

for intermediary nodes g on paths between node i and j.

3.1. EWMA chart

The EWMA chart proposed by Roberts (1959) is useful for monitoring and detecting small shifts in the process parameter. Despite having similar performance to CUSUM charts, EWMA charts are widely used due to their ease and simplicity of application and implementation.

We define X_t, t = 1, 2, . . . , as the independent observations at time t. The EWMA chart statistic, the upper control limit (UCL), and the lower control limit (LCL) are defined as follows:

where μ₀ is the in-control mean, σ₀ is the in-control standard deviation of X_t, γ (0 < γ ≤ 1) is the smoothing coefficient, and L is the factor that determines the width of the control limits. The initial value of chart statistic, Z₀, is usually set to be equal to μ₀. For smoothing coefficients, it is well known that smaller values of γ are better at detecting small changes, and larger values are better at detecting large changes. If the value of γ is chosen, L can be determined by the practitioner according to the specified value of in-control ARL, ARL₀.

As t increases, the above control limits converge to the asymptotic limits given by

In this paper, we use these asymtotic control limits to evaluate the performance of EWMA charts.

3.2. Multinomial CUSUM chart

Traditionally, SPM uses Shewhart p-charts and binomial CUSUM charts to monitor the proportion of non-conforming items in the process. To use these charts, we must wait until the required number of items (n > 1) are aggregated into samples to monitor the proportion of nonconforming items. As a result, these charts have the disadvantage of having an inherent delay in detecting shifts in the proportion, which causes slower detection of process changes. To overcome this disadvantage, Reynolds and Stoumbos (1999) proposed using a Bernoulli CUSUM chart when a continuous stream of inspected items is available. The Bernoulli CUSUM chart is a special case of the binomial CUSUM chart when n = 1.

Although these charts mentioned above can only be used in situations where items are classified into two categories, there are many situations where items are classified into more than two categories. For example, instead of classifying items in a process as good or bad, they can be categorized as good, fair, or bad. Similarly, the diagnosis of posttraumatic patients can be divided into four categories: survival, minor complications, major complications, and death. Ryan et al. (2011) proposed a multinomial CUSUM chart to monitor several categories by extending the Bernoulli CUSUM chart.

Let X₁, X₂, . . . be independent multinomial random variables where X_t = u if the tth item classified into the uth category, t = 1, 2, . . . , u = 1, 2, . . . , v. Let p_0,u and p_1,u be the in-control and out-of-control probabilities of being classified into the uth category, respectively, where p_0,u ≠ p_1,u, Σu=1v p0,u=1 and Σu=1v p1,u=1.

The multinomial CUSUM statistics are defined as

where S₀ = 0 and R_t is the log-likelihood ratio score. The values of R_t are

when X_t = u. The multinomial CUSUM chart signals when S_t > h, where the control limit, h, can be determined satifying the specified value of ARL₀.

Note that the multinomial CUSUM procedure can be generalized to include samples of size n > 1 (Ryan et al., 2011).

Let w_{i j,t} be the number of communications between nodes i and j at time t. In this paper, we assume that the network is undirected and does not consider any node to communicate with itself, and also assume that w_{i j,t} follows a Poisson distribution as

where λ represents the in-control mean of weights.

We can calculate degree centralities D_w,t(i) and closeness centralities C_w,t(i) for i = 1, 2, . . . , N at time t defined in (2.1) and (2.2), respectively, and then can obtain the average degree centrality Deg¯t and the average closeness centrality Close¯t as

These average measures can be classified into the following four categories to be applied to the multinomial CUSUM chart.

• (i) Category 1 : Deg¯t≥μd and Close¯t≥μc,

• (ii) Category 2 : Deg¯t<μd and Close¯t≥μc,

• (iii) Category 3 : Deg¯t<μd and Close¯t<μc,

• (iv) Category 4 :Deg¯t≥μd and Close¯t<μc,

where μ_d is the in-control mean of degree and μ_c is the in-control mean of closeness which can be estimated from Phase I samples. In this paper, the values of μ_d, μ_c, and p_0,u (u = 1, 2, 3, 4) in (3.5) are estimated from 100,000 simulated networks.

The procedure proposed in this paper is summarized as follows: First, D_w,t(i) and C_w,t(i) are calculated for N nodes at time t, and Deg¯t and Close¯t are calculated. After that, by determining which category these values belong to according to the above classification rule, the R_t in (3.5) and the multinomial CUSUM statistic, S_t, in (3.4) are calculated. Finally, by comparing the value of this statistic with the control limit h, it is determined whether or not to give a signal.

5.1. Simulation settings

Through simulation, the performance of the proposed multinomial CUSUM procedure is evaluated by comparing it with the EWMA procedure using degree centrality and clossness centrality separately. In the EWMA procedure, Deg¯t in (4.1) and Close¯t in (4.2) are used as X_t in (3.1), respectively. The multinomial CUSUM chart and the EWMA charts are compared based on their ARL values.

The settings of the simulation are determined by considering (i) the network to have N = 30 nodes, (ii) the in-control mean of weights as λ = 1 and 2, and (iii) in the presence of an anomalous event within the social network, the mean of weights between K (≤ 30) randomly chosen abnormal nodes to change from λ to (1+δ)λ. In our simulations, K, which refers to the number of abnormal nodes, takes on values of 2, 3, 4, and 6, while δ, which denotes the change in parameter, takes on values of 0.5, 1, 2, 3, 4, 5, 6, 7, and 8. For example, the case where λ = 1, K = 2, and δ = 2 means that among 30 nodes, the weight of two nodes has changed to 3, and the weight of the remaining nodes is 1 without change.

Note that in order to apply the multinomial CUSUM chart, it is necessary to specify the out-of-control probabilities of each category, p_1,u (u = 1, 2, 3, 4), in (3.5). Table 1 shows the in-control probabilities, p_0,u, estimated from Phase I samples and the out-of-control probabilities, p_1,u, desired to be detected. These out-of-control probabilities are set to probabilities of δ = 2 when λ = 1 and to probabilities of δ = 1 when λ = 2 for each abnormal nodes size K.

To determine the control limits for control charts, the in-control ARL value is set as 100. We design three different EWMA charts with γ = 0.05, 0.1, and 0.2, and obtain the values of L in (3.2) and (3.3) using the software provided by Knoth (2021). The control limits, h, for the multinomial CUSUM chart, are determined using 100,000 simulations. The values of L in (3.2) and (3.3) for the EWMA chart and the values of h for the multinomial CUSUM chart are displayed in Table 2. As shown in Table 1, in the multinomial CUSUM chart, since the values of p_0,u and p_1,u vary according to λ and K, the values of h satisfying ARL₀ = 100 in each case are different. However, in the EWMA chart, the average centralities in (4.1) and (4.2) approximately follow a normal distribution, respectively, and L, which represents the width of the control limits, depends only on γ. Therefore, the values of L satisfying ARL₀ = 100 are determined to be the same value for a given γ.

The out-of-control ARL values for the EWMA chart are obtained from 10,000 simulations, while the values for the multinomial CUSUM chart are obtained from 100,000 simulations.

5.2. Simulation results

We look at how the occurrence of abnormal nodes changes the probability of each category. Figure 1 illustrates a scatterplot of the in-control and out-of-control probabilities for degree and closeness centralities of λ = 1. In Figure 1(a) shows the scatterplot for the in-control state, and shows that the probabilities of category 1 and 3 components are similar. However, from Figure 1(b), it can be seen that when abnormal nodes of K = 4 and δ = 6 occur, the probability of category 1 increases significantly, but that of category 3 decreases significantly. It is found that when K = 2, 3, and 4, the probabilities of category 1 and 2 increase, while the probabilities of category 3 and 4 decrease. When K = 6, the probability of category 1 increases, but the probabilities of category 2, 3, and 4 decrease. Due to the change in the probabilities belonging to each category, the multinomial CUSUM chart can detect the occurrence of abnormal nodes.

The ARL performance for λ = 1 and λ = 2 are shown in Tables 3 and 4, respectively. In each row of the tables, the smallest ARL value is shown in boldface.

In Table 3 where λ = 1, the in-control mean of degree is μ_d = 29.00397, whereas the in-control mean of closeness is μ_c = 0.0471556. When K = 2 and δ is not large (δ ≤ 3), the multinomial CUSUM chart performs better than the EWMA charts. When δ is large, the EWMA chart using closeness centrality with γ = 0.05 performs better. However, even when δ is large, the performance of the EWMA chart using degree centrality is not good compared to the multinomial CUSUM chart. For example, when δ = 4, the ARL for the multinomial CUSUM chart is 38.4, while the ARL for the EWMA chart using degree centrality with γ = 0.05 is 52.3. The multinomial CUSUM chart performs better for small δ at K = 3 and 4, but the EWMA charts perform better as δ increases. When K = 6, the EWMA charts outperform the multinomial CUSUM chart for all the changes. When the abnormal nodes size is large (K ≥ 4), the overall performance of the EWMA charts using γ = 0.2 is better.

To determine why the multinomial CUSUM chart performs poorly for large K and δ, we examine the probabilities of four categories for each change, as shown in Table 5 where λ = 1. As mentioned in Ryan et al. (2011), the multinomial CUSUM chart has a weakness in detecting shifts in misspecified directions and magnitudes. As K and δ increase, the direction and magnitude of the probabilities change differently from those specified in Table 1. For example, it can be seen that when K = 3 and δ = 8, the probability of category 1 increases significantly compared to the magnitude specified in Table 1, and the probability of category 2 changes in the opposite direction to the direction specified in Table 1. In addition, when K = 6 and δ is large, the probability of category 1 is significantly larger than other probabilities. As such, when the probability of one category is representative of the entire network, the ARL performance of the multinomial CUSUM chart may deteriorate.

In Table 4 where λ = 2, the in-control mean of degree is μ_d = 57.99715, whereas the in-control mean of closeness is μ_c = 0.08057656. Similar to the results in Table 3, the multinomial CUSUM chart performs better for small values of K and δ, while the EWMA charts perform better for large values of K or δ. When K or δ are very large, the fact that the performance of the multimomial CUSUM chart deteriorates still occurs as shown in Table 3.

From the results in Tables 3 and 4, it is recommended to use the multinomial CUSUM chart when the direction and magnitude of change in category probabilities can be predicted to some extent, or when the magnitude of change is expected to be small. The advantage of using the multinomial CUSUM chart is that we can monitor several centrality measures simultaneously instead of monitoring one centrality measure with a single chart.

In recent years, there have been many studies focused on monitoring and detecting changes in SNA and providing information to help prevent conflicts and crises. Accordingly, the networks were observed over time and the observed networks were monitored by applying control charts. Most studies that applied control charts individually used continuous measures as statistics. However, when several continuous measures are classified into one categorical variable and applied to a control chart, there is an advantage that several measures can be monitored using a single control chart.

In this paper, we proposed a procedure for classifying degree and closeness measures, that represent local and global perspectives, respectively, based on their average values and detecting the occurrence of abnormal nodes using the probabilities change of the classified categories. The performance of the proposed procedure was compared with that of the EWMA charting procedure using degree and centrality measures individually through simulation.

From the simulation results, it was found that the multinomial CUSUM chart showed better performance for small changes but poor performance for large changes. When K and δ were large, the performance of the CUSUM chart deteriorated because the probability of each category changed differently from the direction and magnitude specified in advance. Therefore, the proposed procedure is recommended when the direction and magnitude of change in category probabilities can be predicted or when it is desired to detect small changes in the social network.

Finally, it would be interesting to study procedures that use measures other than degree and close ness centrality measures as criteria for categorization. In the future, we will study the classification procedures using two or more different measures and their performance for various types of change.