This package contains algorithms for detecting core-periphery structure in networks. All algorithms are implemented in Python, with speed accelerations by numba, and can be used with a small coding effort.
Before installing this package, make sure that you have a **Python with version 3.6, 3.7, 3.8, and 3.9
pip is the most easiest way to install:
pip install cpnetFor conda users, although the package can be install using pip without problem in conda environement, you may want to avoid mixing pip with conda. In this case, we recommend making a link to the package:
git clone https://github.com/skojaku/core-periphery-detection
cd core-periphery-detection
conda develop .See requirements.txt
This package consists of the following two submodules:
- A set of algorithms for detecting core-periphery structure in networks
- Codes for a statistical test for core-periphery structure
See How to use cpnet for quick start.
Load an algorithm for detecting core-periphery structure in networks:
import cpnet
algorithm = cpnet.KM_config()Pass a graph object (networkx.Graph or adjacency matrix in scipy.sparse format) to the algorithm:
import networkx as nx
G = nx.karate_club_graph()
algorithm.detect(G)Retrieve the results:
c = algorithm.get_pair_id()
x = algorithm.get_coreness()c and x are python dict objects that take node labels (i.e., G.nodes()) as keys.
- The values of
care integers indicating group ids: nodes having the same integer belong to the same group. - The values of
xare float values indicating coreness ranging between 0 and 1. A larger value indicates that the node is closer to the core. In case of discrete core-periphery structure, the corenss can only take 0 or 1, with x[i]=1 or =0 indicating that node i belongs to a core or a periphery, respectively.
For example,
c = {A: 0, B: 1, C: 0, ...}
x = {A: 1, B: 1, C: 0, ...}means that nodes A and C belong to group 0, and B belongs to a different group 1. Furtheremore, A and B are core nodes, and C is a peripheral node.
All algorithms implemented in this package have the same inferface. This means that you can use other algorithms by changing cpnet.KM_config to, for example, cpnet.BE. See the list of algorithms.
The core-periphery structure detected by any algorithm can be systematic artifacts; even for networks without core-periphery structure such as regular graphs and random graphs, an algorithm labels nodes as core or periphery.
To filter out spurious core-periphery structure, this package provides an implementation of a statistical test, q-s test. In this test, one generate many randomized networks and detect core-periphery structure with the algorithm used to detect the core-periphery structure in question. The core-periphery structure detected for the input network is considered as significant if it is stronger than those detected in randomized networks. See papers here and here for the method.
To carry out the statistical test, run
sig_c, sig_x, significant, p_values = cpnet.qstest(c, x, G, algorithm, significance_level = 0.05, num_of_thread = 4)candxare the core-periphery pairs in question that will be tested by the statistical testGis the graph object (Networkx.Graph)algorithmis the algorithm that you used to getcandxsignificance_levelis the significance level. (Optional; default is 0.05)num_of_threadNumber of threads to perform the statistical test (Optional; default is 4)sig_candsig_xare dict objects taking node names as its keys. The values of the dict objects are the same as thecandxbutNonefor the nodes belonging to the insignificant core-periphery pairs.significantis a boolean list, wheresignificant[k]=Trueorsignificant[k]=Falseindicates that the k-th core-periphery pair is significant or insignificant, respectively.p_valuesis a float list, wherep_values[k]is the p-value for the k-th core-periphery pair under a null model (default is the configuration model).
Some core-periphery pairs have a p-value smaller than the prescribed significance level but deemed as insignificant. This is because the statistical significance is adjusted to control for the false positives due to the multiple comparison problem.
The p-value is computed using the configuration model as the null model. One can use a different null model by passing a user-defined function as the null_model argument to qstest.
For example, to use the Erdős–Rényi random graph as the null model, define
def erdos_renyi(G):
n = G.number_of_nodes()
p = nx.density(G)
return nx.fast_gnp_random_graph(n, p)Then, pass it to the argument of the qstest:
sig_c, sig_x, significant, p_values = cpnet.qstest(
c, x, G, algorithm, significance_level=0.05, null_model=erdos_renyi
)cpnet implements a drawing function based on networkx.
ax, pos = cpnet.draw(G, c, x, ax, max_group_num = None, draw_edge=False, draw_nodes_kwd={}, draw_edges_kwd={}, draw_labels_kwd={})Gis the graph object (Networkx.Graph)candxare the core-periphery pairsaxis the matplotlib axismax_group_num: The topmax_group_numlargest groups will be drawn.draw_edgeis a boolean (Optional; Default False). Setdraw_edge = Truenot to draw the edges (recommended if the network is large)draw_nodes_kwd={},draw_edges_kwd={}, anddraw_labels_kwd={}are the keywords that are passed to networkx.draw_network_nodes, networkx.draw_network_edges, and networkx.draw_network_labels, respectively (see the networkx documentation). Useful when refining the figure.posis a dict object. The keys are the node ids given by G.nodes(). The values are tuples (x, y) indicating the positions of nodes.- See the code for other parameters.
The drawing functions are demonstrated in the example notebook. See
Some algorithms have tuning parameters. Please see the source code for the parameters specific to each algorithm.
One can detect
- a single pair of a core and a periphery using
cpnet.BE,cpnet.Lip,cpnet.LapCore,cpnet.LapSgnCore,cpnet.Surprise,cpnet.LowRankCore
- multiple pairs of a core and a periphery using
cpnet.KM_ER,cpnet.KM_config,cpnet.Divisive
- a continuous spectrum between a core and a periphery using
cpnet.MINRES,cpnet.Rombach,cpnet.Rossa
The following algorithms take the edge weight into account:
cpnet.KM_ER,cpnet.KM_config,cpnet.Divisive,cpnet.Rombach,cpnet.Rossa,cpnet.LapCore,cpnet.LapSgnCore,cpnet.LowRankCore
A follow-up study of Surprise provides a unified framework to detect communities and core-periphery structure based on surprise. The authors of the paper reported that the new algorithm scales better than the Surprise algorithm. See their github repo for the code.