common_neighbor_centrality#
- common_neighbor_centrality(G, ebunch=None, alpha=0.8)[source]#
Return the CCPA score for each pair of nodes.
Compute the Common Neighbor and Centrality based Parameterized Algorithm(CCPA) score of all node pairs in ebunch.
CCPA score of
u
andv
is defined as\[\alpha \cdot (|\Gamma (u){\cap }^{}\Gamma (v)|)+(1-\alpha )\cdot \frac{N}{{d}_{uv}}\]where \(\Gamma(u)\) denotes the set of neighbors of \(u\), \(\Gamma(v)\) denotes the set of neighbors of \(v\), \(\alpha\) is parameter varies between [0,1], \(N\) denotes total number of nodes in the Graph and \({d}_{uv}\) denotes shortest distance between \(u\) and \(v\).
This algorithm is based on two vital properties of nodes, namely the number of common neighbors and their centrality. Common neighbor refers to the common nodes between two nodes. Centrality refers to the prestige that a node enjoys in a network.
See also
common_neighbors()
- Parameters:
- Ggraph
NetworkX undirected graph.
- ebunchiterable of node pairs, optional (default = None)
Preferential attachment score will be computed for each pair of nodes given in the iterable. The pairs must be given as 2-tuples (u, v) where u and v are nodes in the graph. If ebunch is None then all nonexistent edges in the graph will be used. Default value: None.
- alphaParameter defined for participation of Common Neighbor
and Centrality Algorithm share. Values for alpha should normally be between 0 and 1. Default value set to 0.8 because author found better performance at 0.8 for all the dataset. Default value: 0.8
- Returns:
- piteriterator
An iterator of 3-tuples in the form (u, v, p) where (u, v) is a pair of nodes and p is their Common Neighbor and Centrality based Parameterized Algorithm(CCPA) score.
- Raises:
- NetworkXNotImplemented
If
G
is aDiGraph
, aMultigraph
or aMultiDiGraph
.- NetworkXAlgorithmError
If self loops exist in
ebunch
or inG
(ifebunch
isNone
).- NodeNotFound
If
ebunch
has a node that is not inG
.
References
[1]Ahmad, I., Akhtar, M.U., Noor, S. et al. Missing Link Prediction using Common Neighbor and Centrality based Parameterized Algorithm. Sci Rep 10, 364 (2020). https://doi.org/10.1038/s41598-019-57304-y
Examples
>>> G = nx.complete_graph(5) >>> preds = nx.common_neighbor_centrality(G, [(0, 1), (2, 3)]) >>> for u, v, p in preds: ... print(f"({u}, {v}) -> {p}") (0, 1) -> 3.4000000000000004 (2, 3) -> 3.4000000000000004 ----
Additional backends implement this function
- parallelA networkx backend that uses joblib to run graph algorithms in parallel. Find the nx-parallel’s configuration guide here
The edge pairs are chunked into
pairs_chunks
and then the common neighbor centrality for allpairs_chunks
is computed in parallel overn_jobs
number of CPU cores.- Additional parameters:
- get_chunksstr, function (default = “chunks”)
A function that takes in a list of all the edges (or ebunch) as input and returns an iterable
pairs_chunks
. The default chunking is done by slicingebunch
inton_jobs
number of chunks.
[Source]