Relational flexibility of network elements based on inconsistent community detection

Community identification of network components enables us to understand the mesoscale clustering structure of networks. A number of algorithms have been developed to determine the most likely community structures in networks. Such a probabilistic or stochastic nature of this problem can naturally involve the ambiguity in resultant community structures. More specifically, stochastic algorithms can result in different community structures for each realization in principle. In this study, instead of trying to “solve” this community degeneracy problem, we turn the tables by taking the degeneracy as a chance to quantify how strong companionship each node has with other nodes. For that purpose, we define the concept of companionship inconsistency that indicates how inconsistently a node is identified as a member of a community regarding the other nodes. Analyzing model and real networks, we show that companionship inconsistency discloses unique characteristics of nodes, thus we suggest it as a new type of node centrality. In social networks, for example, companionship inconsistency can classify outsider nodes without firm community membership and promiscuous nodes with multiple connections to several communities. In infrastructure networks such as power grids, it can diagnose how the connection structure is evenly balanced in terms of power transmission. Companionship inconsistency, therefore, abstracts individual nodes' intrinsic property on its relationship to a higher-order organization of the network.

Figure 1

An illustrative guide to the CoI, in particular, compared to the betweenness centrality (BC). (a) An example network. (b) The BC only counts the shortest path length likely going through the central node 8, so it cannot discern the two bridge nodes (6 and 7) in terms of community structure. (c) A schematic diagram of measuring CoI. From an ensemble of several community detection results (step 1), we extract the inconsistent community partnership (step 2). Based on this co-occurence between the nodes, we assign each node's CoI value by evaluating the overall inconsistency with the other nodes (step 3).

Figure 2

An example showing the conceptual difference between companionship inconsistency and externality. From the three different community detection results illustrated, the central node (red arrow) has the CoI value ${\mathrm{\Phi }}_{\mathrm{central}}=8/9$ and mean externality $\langle E_{\mathrm{central}}\rangle =4/9$.

Figure 3

A realization of the clustered network model with 10 communities inside, and the correlation between CoI and other network measures from 20 network realizations and 20 community detection results for each network. (a) The nodes belong to one of 10 communities marked by distinct colors. (b) The same network with the same layout as in panel (a) but with the different shades of color indicating the node externality value. (c) The hexagonal bin plots show the linear regression between CoI and degree, betweenness, and mean externality with the Pearson correlation coefficients $0.155,0.458$, and 0.553, respectively, as reported in Table 1. The shade of each hexagon indicates the number of corresponding data points inside each cell. The result is from $500\times 20={10}^4$ data points in total, as we collect all of the nodes' centrality values for 20 different network realizations.

Figure 4

An example of community detection result for the ZZKC network is shown in panel (a) and the CoI values from 20 results are shown in panel (b), where the outsider node is notable with the brightest color, and the edges from the node are shown in red. Similarly, an example of community detection result for the Star Wars network is shown in panel (c) and the CoI values from 20 results are shown in panel (d), where one of the multiplayer nodes (Luke Skywalker) is notable with the brightest color and the edges from him are shown in red. The size of nodes is proportional to their degree, and the color shade of the nodes in panels (b) and (d) indicates the CoI values in the linearly scaled color bar at bottom right.

Figure 5

The correlations between CoI and degree, BC, and mean externality of the real networks are presented in the left (a)–(e), and we show the networks themselves (f)–(j) with the nodes color coded by their CoI values. On the correlation plots, the hexagonal bins in each panel show the density of the data points inside. We also show the linear regression lines and the shading around them indicating the 95% confidence interval. CoI shows the positive correlation to externality revealing the functionally distinct nodes in a network. The size of nodes is proportional to the degree. The size of nodes is proportional to their degree, and the color shade of the nodes in panels (b) and (d) indicates the linearly scaled CoI values in the color bar at bottom right.