2024 Volume 33 Issue 8
Article Contents

Peijie Ma, Xuezao Ren, Junfang Zhu, Yanqun Jiang. Detecting the core of a network by the centralities of the nodes[J]. Chinese Physics B, 2024, 33(8): 088903. doi: 10.1088/1674-1056/ad4cd4
Citation: Peijie Ma, Xuezao Ren, Junfang Zhu, Yanqun Jiang. Detecting the core of a network by the centralities of the nodes[J]. Chinese Physics B, 2024, 33(8): 088903. doi: 10.1088/1674-1056/ad4cd4

Detecting the core of a network by the centralities of the nodes

  • Received Date: 23/01/2024
    Accepted Date: 15/04/2024
    Available Online: 01/07/2024
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(5)  /  Tables(4)

Article Metrics

Article views(821) PDF downloads(1) Cited by(0)

Access History

Detecting the core of a network by the centralities of the nodes

Abstract: Many networks exhibit the core/periphery structure. Core/periphery structure is a type of meso-scale structure that consists of densely connected core nodes and sparsely connected peripheral nodes. Core nodes tend to be well-connected, both among themselves and to peripheral nodes, which tend not to be well-connected to other nodes. In this brief report, we propose a new method to detect the core of a network by the centrality of each node. It is discovered that such nodes with non-negative centralities often consist in the core of the networks. The simulation is carried out on different real networks. The results are checked by the objective function. The checked results may show the effectiveness of the simulation results by the centralities of the nodes on the real networks. Furthermore, we discuss the characters of networks with the single core/periphery structure and point out the scope of the application of our method at the end of this paper.

1.   Introduction
  • Many networks exhibit the core/periphery structure, which is important for scientists to understand the properties and the dynamics of the networks.[1] The constitution of the structure often refers to a simple two-class partition.[2–4] The definition of core/periphery has been formalized in Ref. [2]. The notion of the core in the network is often used to describe the connectivity between the nodes with large degree, and it has been applied to profile meso-scale properties in networks by examining the density of connections.[5–10] The core in the network influences the functionality of itself. It is demonstrated in the transmission of rumors or information in social networks,[11,12] in the organization of the human connection in neurodevelopment,[13,14] in the transportation networks of airline flights,[15] and in the characterizing data patterns.[16]

    The core of the network is often regarded to be comprised of the densely inter-connected high-degree nodes, which impact adaptability, flexibility, and controllability.[17,18] Lots of profiling methods have been proposed based on optimizing a suitable fitness function using the coreness value to define the density of links inside the core,[2] referring to a quality index with respect to the size of the expected core and the fuzziness of the boundary,[19] or applying Markov chains to describe random walks to index the coreness of individual nodes.[20] These methods rely on subjective fine-tuning due to the presence of one or more free parameters, which could be obtained arbitrarily or by techniques. Other examples include maximizing the closeness centrality within the core by an ensemble of random networks to define a coefficient that characterizes the core.[3] Recently, some scientists have proposed to use an influence propagation process to detect the pairs of core-periphery nodes.[21] Generally, these methods always tend to be relatively complex in nature, and therefore scalability issues are likely to be encountered when applied to the huge networks.

    Interestingly, the presence of a network with core/periphery structure could be divided into two parts. However, there is, at present, no general method to define the core nodes. Due to the importance of the core/periphery structure in the networks, we present a method to profile such structure in this brief report. First, we define the centrality of each node. It could be considered that the core of a network consists of the nodes with non-negative centralities. Second, the results can be checked by the objective function. It is discovered that the nodes with non-negative centralities may be included to the core by detecting the core/periphery structure. Third, we discuss the character of the network with single core/periphery structure on the synthetic network. Furthermore, we describe the scope of the application of our method.

2.   Method
  • Consider an unweighted and undirected network. A complex network can be described as a graph set G(V,E). The node set is V, and the connection set is E. In this paper, it is considered that these connections are undirected in the network. Each element in the adjacency matrix A of the network is 0 or 1, when node i is connected with node j, the element aij = 1, otherwise aij = 0. The degree of node i is ki = ∑jaij. Then, we can define the centrality C(i) of the node i in the network. It is considered that the core node in the star network may have the highest centrality, while the periphery nodes have the lowest centrality. The centrality of node i is defined as

    It is discovered that the value of the node centrality C(i) only depends on the degree of node i itself and its neighbors’ degrees instead of all the nodes in the network.

    Obviously, the star network possesses the most significant core/periphery structure. Thus, the centrality of the core node in the star network is equal to 1, while the centrality of the periphery node in the star network is equal to −1. Usually, the heterogeneity between a pair of nodes in the complex network is not as large as the one in the star network. Yet the centrality of the node in the regular network with the period boundary condition or in the globally connected network may be equal to 0 because of the same degree of each node. In this paper, it is defined that the node is a core node if its centrality is larger or equal to zero.[22] The node with negative centrality is regarded as a peripheral one.[23]

    For instance, we can calculate the nodes of the centralities in the karate club network[24] by formula (1). The results are listed in order in Table 1. We may establish a core set of these core nodes. The core set is {34, 1, 33, 2, 3, 6, 7, 4}. Thus, it may be considered that the core of the karate club network contains these eight nodes at least.

    Then, we ought to check the correctness of the result whether only the core. The reason for this is that there is a possibility that the core of the network may contain the nodes with negative centralities. According to Ref. [25], the objective function may check the correctness of the result. The objective function is introduced as follows:

    Here, nc is the number of the core nodes, np is the number of the peripheral nodes, Ecc is the number of the connections in the core, Epp is the number of the connections between each pair of the peripheral nodes, and Ecp is the number of the connections between the core nodes and the peripheral nodes. The first term 2Ecc/nc/(nc – 1) is the connection density of the core nodes. The second term Ecp/nc/np is the connection density between the core and the peripheral nodes. The last term 2Epp/np/(np – 1) is the connection density of the peripheral nodes. If we choose the core nodes correctly, the objective function always maximizes the connection density among the core nodes, and between core and peripheral nodes, while minimizing the connection density among the peripheral nodes.

    The checking steps could be introduced with the karate club network as follows. As shown in Table 1, we have obtained eight nodes with the positive centralities. Thus, it could be thought that the core of the network contains these eight nodes at least. First, we may calculate the value of the objective function, and its value is 0.6282. (Here, nc = 8, np = 26, Ecc = 11, Ecp = 56, and Epp = 11.) It is obvious that there are 24 neighbors connecting the core. Next, we may choose a node from the neighbors, and add it to the core. Thus, the core set is {34, 1, 33, 2, 3, 6, 7, 4, X}. Here, X is the neighbor connecting with the core nodes. We may obtain a new value of the objective function. Here, nc is 9 and np is 25 in the karate club network. For example, it is assumed that node 5 is chosen and the new core set is {34, 1, 33, 2, 3, 6, 7, 4, 5}. According to formula (2), the value of the objective function is 0.5722. We could repeat the process above, and obtain 24 different values of the objective function. In each calculation process, we keep nc at 9 and np at 25, and change the neighbor node only. The calculation results show that the increment of the objective function is positive, if the new core set is {34, 1, 33, 2, 3, 6, 7, 4, 14}. The value of the objective function is 0.6344. (Here nc = 9, np = 25, Ecc = 16, Ecp = 51, and Epp = 11.) The other results of the increments of the objective function are all negative. As shown in Fig. 1, it is discovered that the neighbors of node 14 are all core nodes with positive centralities. The connection density of the core nodes would be more if node 14 is regarded as a core one. Now the core set is {34, 1, 33, 2, 3, 6, 7, 4, 14}. What will happen if we add one node to the core once again? As expected, the value of the objective function will decrease. The objective function gets the maximum locally, if the core of the karate club network is the set {1, 2, 3, 4, 6, 7, 14, 33, 34}. We have obtained the core of the karate club network by the centrality, and checked the result by the objective function. The results of the two methods differ by only one node.

    It is thought that generally the core of the karate club network contains five nodes at least (node 1, node 2, node 3, node 33 and node 34).[26,27] Yet, some scientists have concluded that the core of the karate club network contains 14 nodes.[20] Thus, it could be acceptable that the core of the network is made up of the nodes with non-negative centralities.

3.   Simulation and analysis
  • In this section, we examine the core/periphery structure in some real-world networks, and analyze the effectiveness of the results on a synthetic benchmark network.

  • We may apply our method to the dolphin network, which has an obvious core/periphery structure. The dolphin network describes the associations between 62 dolphins living in Doubtful Sound.[28] In this network, the dolphins represented as nodes have connections with each other if they are observed together more often than expected by chance during the years from 1994 to 2001. There are 159 connections in the dolphin network. First, we calculate the centrality of each node by formula (1), and the simulation results are listed in Table 2. It shows that there are 21 core nodes in the dolphin network. The core set is {52, 18, 58, 15, 46, 30, 38, 34, 2, 21, 39, 14, 37, 16, 10, 55, 44, 43, 41, 48, 28}. According to formula (2), the value of the objective function is 0.2667. (Here nc = 21, np = 41, Ecc = 38, Ecp = 98, and Epp = 23.) Then, we used the objective function to check the core of the dolphin network. Via the simulation, we obtain the core set, which is {2, 10, 14, 15, 16, 18, 21, 28, 30, 34, 37, 38, 39, 41, 43, 44, 46, 48, 51, 52, 55, 58}. The additional node is node 51, whose centrality is negative but its neighbors are node 15, node 17, node 21, node 34, node 43, node 46 and node 52. Six of them are core nodes. Thus, it could enhance the connection density of the core nodes and let the objective function get the local maximum. The value of the objective function is 0.2680. (Here nc = 22, np = 40, Ecc = 44, Ecp = 93, and Epp = 22.)

  • We also apply our core/periphery structure-finding method to the collaboration network of the scientists at Santa Fe Institute during any part of calendar year 1999 or 2000.[29] We carry our research to the largest component of the collaboration graph. This network contains 118 nodes, and each node presents a scientist. There exists a connection between a pair of nodes if they have coauthored one or more articles during the same time period. There are 200 connections in this collaboration network. From Fig. 3, it may be discovered that each scientist has coauthored articles with about four others. Via the simulation, we may find that there are 21 nodes with the positive centralities in the network by formula (1). The core set is {2, 24, 12, 1, 27, 56, 53, 22, 9, 4, 6, 17, 15, 5, 11, 66, 72, 51, 23, 47, 28}. According to formula (2), the value of the objective function is 0.1739. (Here, nc = 21, np = 97, Ecc = 25, Ecp = 131, and Epp = 44.) Then, we detect the core of the collaboration network from these core nodes by the objective function. Via the simulation, we obtain the core set of the collaboration network is {1, 2, 3, 4, 5, 6, 9, 11, 12, 15, 17, 22, 23, 24, 27, 28, 47, 51, 53, 56, 66, 72}. The additional node is node 3, whose centrality is negative but its neighbors are node 4, node 5, node 6, node 24, node 73 and node 74. Four of them are core nodes. Thus, it could enhance the connection density of the core nodes and let the objective function get local maximum. The value of the objective function is 0.1774. (Here, nc = 22, np = 96, Ecc = 29, Ecp = 129, and Epp = 42.)

  • As a further test of our algorithm, we turn to the politician blogs network. The politician blogs network is a directed network of hyperlinks between weblogs on US politics.[30] This network contains 1224 nodes, and each node presents a politician. The connections were extracted from a crawl of the front page of the blog around the time of the 2004 presidential election. We convert it to an undirected network by treating all the directed connections as undirected connections, and reserve the largest component. The largest component contains 1222 nodes and 16714 connections. We calculate the centrality of each node. The simulation results show that there are 184 nodes with positive centralities in the politician blogs network, but it is found that these nodes are not connected as a whole. There are two nodes (node 643 and node 1022) isolated with positive centralities. It may be considered that these two nodes are peripheral. The calculation results are given in Appendix A. Thus, the number of the core nodes is 182. According to formula (2), the value of the objective function is 0.2642. (Here, nc = 182, np = 1040, Ecc = 3527, Ecp = 10440, and Epp = 2747.) Then, we could use the objective function to check the core of the politician blogs network. Via the simulation, it is discovered that there are 193 core nodes in the politician blogs network. The value of the objective function is 0.2677. (Here, nc = 193, np = 1029, Ecc = 4110, Ecp = 10066, and Epp = 2538.) Scientists often think that the politician blogs network may be divided into two communities according to the different political leanings, but our results reveal that this network also has a core/periphery structure. These politicians as the core members connect with each other densely, regardless of the political leanings.

  • Since the ground truths about the core/periphery structures in real networks are unknown, we generate a network to measure the correctness of our algorithms.[31] For the synthetic network with single core/periphery structure, the size of whole network, the size of core, and the size of periphery are set as N = 500, nc = 100 and np = 400, respectively. (It is regarded that the nodes with the top 100 numbers are the core nodes, and the others are the periphery nodes in the network.) For a network with typical core/periphery structure, the connection probability among core nodes (Pcc) is larger than or equal to the connection probability between core nodes and peripheral nodes (Pcp), and is also larger than the connection probability among peripheral nodes (Ppp). Therefore, we may set Ppp = 0.05 and Pcc = 4(Pcp – Ppp) + Ppp. The sets of synthetic networks are generated by varying the value of Pcp whose variety range is from 0.05 to 0.2875, for Pcc must be less than or equal to 1. If Pcp is 0.05, the connection probability of the whole network is 0.05, and thus the network would not express the core/periphery structure. Yet, the synthetic network would show the core/periphery structure clearly with the increase of the value of Pcp. In order to describe the extent of the core/periphery structure, we can introduce the global centrality C of the network. The global centrality C may be defined as

    This is the mean value of the absolute value of each node’s centrality. This shows that the more the global centrality is, the more obvious the core/periphery structure is. Figure 4 shows the relationship between the global centrality C and the connection probability Pcp. The calculation results are in line with our expectations.

    After getting the centrality of each node by formula (1), we verify the correctness of our algorithms. First, we may define TP, TN, FP and FN, these four variables, to classify the simulation results. TP is defined as the number of the identified core nodes in the core nodes. TN is defined as the number of the identified periphery nodes in the periphery nodes, FP is defined as the number of the identified core nodes in the periphery nodes, and FN is defined as the number of the identified periphery nodes in the core nodes. Next, we calculate the accuracy, recall, specificity and precision with the defined variables above. Here, accuracy is (TP+TN)/N, recall is TP/nc, specificity is TN/np, and precision is TP/(TP+FP). Finally, the results are shown in Fig. 5.

    It is discovered that the accuracy grows with the increase of the global centrality. If the global centrality of the network is larger than 0.18, the accuracy could be approximately equal to 1. What should be noticed is that the recall grows most sharply. This means that the core of the network can be identified accurately by the centrality of each node when the network represents a little bit of the core/periphery structure. Yet the specificity and the precision do not grow as sharply as the recall. The reason is that some periphery nodes are identified as core nodes if the core/periphery structure of the network is not very obvious. With the increase of Pcp, the core/periphery structure of the network may get more and more clear. Meanwhile the accuracy, recall, specificity, and precision of these four variables tend towards 1. This means the core nodes and the peripheral nodes can be distinguished accurately in synthetic networks with a large global centrality.

4.   Conclusion
  • In this brief report, we have defined the centrality of each node. It could be regarded that nodes with the positive centralities consist of the core of the complex network. We have carried out a simulation on real networks, i.e., the karate club network, the dolphin network, the scientific collaboration network, and the politician blogs network. Meanwhile, we have used the objective function to check the core of the network in order to ensure the reliability of the results. The checked results have shown the effectiveness of the simulation results by the centralities of the nodes on the real networks mentioned above. Furthermore, we have taken the calculation on the synthetic networks with single core/periphery structure, and have obtained consistent conclusions.

    Generally, the centrality of each node represents the importance in the network. The core nodes with large degree may be regarded as the global central nodes, such as node 34 and node 1 in the karate club network. Yet, the core nodes with little degrees may be regarded as the local central nodes, such as node 6 and node 7 in the karate club network. Such local central nodes often connect two communities to each other. Perhaps, another question may be raised — why do the core nodes consist of the core of the network? The reason for this is that the core nodes and the peripheral nodes can be distinguished accurately when the global centrality of the network is larger than 0.2 from the simulation results in Fig. 5(b). Via formula (3), we may get the global centrality of the networks discussed. The global centrality of the karate club network is 0.504. The global centrality of the dolphin network is 0.343. The global centrality of the scientific collaboration network is 0.526. The global centrality of the politician blogs network is 0.593. It is discovered that the global centrality of these networks is all larger than 0.2. Thus, the viewpoint that the core nodes consist of the core of the network is correct if the network represents the core/periphery structure clearly. Yet, our method may fail, if the global centrality of network is small enough, i.e., the network does not exhibit the core/periphery structure, such as the American college football network,[32] whose global centrality is 0.0317.

    It may be universal to detect the core of complex network by the centrality of each node. This method could be applied to huge networks because of the low order complexity of the simulation. Huge networks often exhibit a multiple core/periphery structure. We hope that our method will also be useful for scientists who wish to detect the core/periphery structure of huge networks.

Figure (5)  Table (4) Reference (32)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return