|
|
import networkx as nx |
|
|
|
|
|
__all__ = ["degree_centrality", "betweenness_centrality", "closeness_centrality"] |
|
|
|
|
|
|
|
|
@nx._dispatchable(name="bipartite_degree_centrality") |
|
|
def degree_centrality(G, nodes): |
|
|
r"""Compute the degree centrality for nodes in a bipartite network. |
|
|
|
|
|
The degree centrality for a node `v` is the fraction of nodes |
|
|
connected to it. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : graph |
|
|
A bipartite network |
|
|
|
|
|
nodes : list or container |
|
|
Container with all nodes in one bipartite node set. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
centrality : dictionary |
|
|
Dictionary keyed by node with bipartite degree centrality as the value. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
>>> G = nx.wheel_graph(5) |
|
|
>>> top_nodes = {0, 1, 2} |
|
|
>>> nx.bipartite.degree_centrality(G, nodes=top_nodes) |
|
|
{0: 2.0, 1: 1.5, 2: 1.5, 3: 1.0, 4: 1.0} |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
betweenness_centrality |
|
|
closeness_centrality |
|
|
:func:`~networkx.algorithms.bipartite.basic.sets` |
|
|
:func:`~networkx.algorithms.bipartite.basic.is_bipartite` |
|
|
|
|
|
Notes |
|
|
----- |
|
|
The nodes input parameter must contain all nodes in one bipartite node set, |
|
|
but the dictionary returned contains all nodes from both bipartite node |
|
|
sets. See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
|
|
for further details on how bipartite graphs are handled in NetworkX. |
|
|
|
|
|
For unipartite networks, the degree centrality values are |
|
|
normalized by dividing by the maximum possible degree (which is |
|
|
`n-1` where `n` is the number of nodes in G). |
|
|
|
|
|
In the bipartite case, the maximum possible degree of a node in a |
|
|
bipartite node set is the number of nodes in the opposite node set |
|
|
[1]_. The degree centrality for a node `v` in the bipartite |
|
|
sets `U` with `n` nodes and `V` with `m` nodes is |
|
|
|
|
|
.. math:: |
|
|
|
|
|
d_{v} = \frac{deg(v)}{m}, \mbox{for} v \in U , |
|
|
|
|
|
d_{v} = \frac{deg(v)}{n}, \mbox{for} v \in V , |
|
|
|
|
|
|
|
|
where `deg(v)` is the degree of node `v`. |
|
|
|
|
|
References |
|
|
---------- |
|
|
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation |
|
|
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook |
|
|
of Social Network Analysis. Sage Publications. |
|
|
https://dx.doi.org/10.4135/9781446294413.n28 |
|
|
""" |
|
|
top = set(nodes) |
|
|
bottom = set(G) - top |
|
|
s = 1.0 / len(bottom) |
|
|
centrality = {n: d * s for n, d in G.degree(top)} |
|
|
s = 1.0 / len(top) |
|
|
centrality.update({n: d * s for n, d in G.degree(bottom)}) |
|
|
return centrality |
|
|
|
|
|
|
|
|
@nx._dispatchable(name="bipartite_betweenness_centrality") |
|
|
def betweenness_centrality(G, nodes): |
|
|
r"""Compute betweenness centrality for nodes in a bipartite network. |
|
|
|
|
|
Betweenness centrality of a node `v` is the sum of the |
|
|
fraction of all-pairs shortest paths that pass through `v`. |
|
|
|
|
|
Values of betweenness are normalized by the maximum possible |
|
|
value which for bipartite graphs is limited by the relative size |
|
|
of the two node sets [1]_. |
|
|
|
|
|
Let `n` be the number of nodes in the node set `U` and |
|
|
`m` be the number of nodes in the node set `V`, then |
|
|
nodes in `U` are normalized by dividing by |
|
|
|
|
|
.. math:: |
|
|
|
|
|
\frac{1}{2} [m^2 (s + 1)^2 + m (s + 1)(2t - s - 1) - t (2s - t + 3)] , |
|
|
|
|
|
where |
|
|
|
|
|
.. math:: |
|
|
|
|
|
s = (n - 1) \div m , t = (n - 1) \mod m , |
|
|
|
|
|
and nodes in `V` are normalized by dividing by |
|
|
|
|
|
.. math:: |
|
|
|
|
|
\frac{1}{2} [n^2 (p + 1)^2 + n (p + 1)(2r - p - 1) - r (2p - r + 3)] , |
|
|
|
|
|
where, |
|
|
|
|
|
.. math:: |
|
|
|
|
|
p = (m - 1) \div n , r = (m - 1) \mod n . |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : graph |
|
|
A bipartite graph |
|
|
|
|
|
nodes : list or container |
|
|
Container with all nodes in one bipartite node set. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
betweenness : dictionary |
|
|
Dictionary keyed by node with bipartite betweenness centrality |
|
|
as the value. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
>>> G = nx.cycle_graph(4) |
|
|
>>> top_nodes = {1, 2} |
|
|
>>> nx.bipartite.betweenness_centrality(G, nodes=top_nodes) |
|
|
{0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25} |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
degree_centrality |
|
|
closeness_centrality |
|
|
:func:`~networkx.algorithms.bipartite.basic.sets` |
|
|
:func:`~networkx.algorithms.bipartite.basic.is_bipartite` |
|
|
|
|
|
Notes |
|
|
----- |
|
|
The nodes input parameter must contain all nodes in one bipartite node set, |
|
|
but the dictionary returned contains all nodes from both node sets. |
|
|
See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
|
|
for further details on how bipartite graphs are handled in NetworkX. |
|
|
|
|
|
|
|
|
References |
|
|
---------- |
|
|
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation |
|
|
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook |
|
|
of Social Network Analysis. Sage Publications. |
|
|
https://dx.doi.org/10.4135/9781446294413.n28 |
|
|
""" |
|
|
top = set(nodes) |
|
|
bottom = set(G) - top |
|
|
n = len(top) |
|
|
m = len(bottom) |
|
|
s, t = divmod(n - 1, m) |
|
|
bet_max_top = ( |
|
|
((m**2) * ((s + 1) ** 2)) |
|
|
+ (m * (s + 1) * (2 * t - s - 1)) |
|
|
- (t * ((2 * s) - t + 3)) |
|
|
) / 2.0 |
|
|
p, r = divmod(m - 1, n) |
|
|
bet_max_bot = ( |
|
|
((n**2) * ((p + 1) ** 2)) |
|
|
+ (n * (p + 1) * (2 * r - p - 1)) |
|
|
- (r * ((2 * p) - r + 3)) |
|
|
) / 2.0 |
|
|
betweenness = nx.betweenness_centrality(G, normalized=False, weight=None) |
|
|
for node in top: |
|
|
betweenness[node] /= bet_max_top |
|
|
for node in bottom: |
|
|
betweenness[node] /= bet_max_bot |
|
|
return betweenness |
|
|
|
|
|
|
|
|
@nx._dispatchable(name="bipartite_closeness_centrality") |
|
|
def closeness_centrality(G, nodes, normalized=True): |
|
|
r"""Compute the closeness centrality for nodes in a bipartite network. |
|
|
|
|
|
The closeness of a node is the distance to all other nodes in the |
|
|
graph or in the case that the graph is not connected to all other nodes |
|
|
in the connected component containing that node. |
|
|
|
|
|
Parameters |
|
|
---------- |
|
|
G : graph |
|
|
A bipartite network |
|
|
|
|
|
nodes : list or container |
|
|
Container with all nodes in one bipartite node set. |
|
|
|
|
|
normalized : bool, optional |
|
|
If True (default) normalize by connected component size. |
|
|
|
|
|
Returns |
|
|
------- |
|
|
closeness : dictionary |
|
|
Dictionary keyed by node with bipartite closeness centrality |
|
|
as the value. |
|
|
|
|
|
Examples |
|
|
-------- |
|
|
>>> G = nx.wheel_graph(5) |
|
|
>>> top_nodes = {0, 1, 2} |
|
|
>>> nx.bipartite.closeness_centrality(G, nodes=top_nodes) |
|
|
{0: 1.5, 1: 1.2, 2: 1.2, 3: 1.0, 4: 1.0} |
|
|
|
|
|
See Also |
|
|
-------- |
|
|
betweenness_centrality |
|
|
degree_centrality |
|
|
:func:`~networkx.algorithms.bipartite.basic.sets` |
|
|
:func:`~networkx.algorithms.bipartite.basic.is_bipartite` |
|
|
|
|
|
Notes |
|
|
----- |
|
|
The nodes input parameter must contain all nodes in one bipartite node set, |
|
|
but the dictionary returned contains all nodes from both node sets. |
|
|
See :mod:`bipartite documentation <networkx.algorithms.bipartite>` |
|
|
for further details on how bipartite graphs are handled in NetworkX. |
|
|
|
|
|
|
|
|
Closeness centrality is normalized by the minimum distance possible. |
|
|
In the bipartite case the minimum distance for a node in one bipartite |
|
|
node set is 1 from all nodes in the other node set and 2 from all |
|
|
other nodes in its own set [1]_. Thus the closeness centrality |
|
|
for node `v` in the two bipartite sets `U` with |
|
|
`n` nodes and `V` with `m` nodes is |
|
|
|
|
|
.. math:: |
|
|
|
|
|
c_{v} = \frac{m + 2(n - 1)}{d}, \mbox{for} v \in U, |
|
|
|
|
|
c_{v} = \frac{n + 2(m - 1)}{d}, \mbox{for} v \in V, |
|
|
|
|
|
where `d` is the sum of the distances from `v` to all |
|
|
other nodes. |
|
|
|
|
|
Higher values of closeness indicate higher centrality. |
|
|
|
|
|
As in the unipartite case, setting normalized=True causes the |
|
|
values to normalized further to n-1 / size(G)-1 where n is the |
|
|
number of nodes in the connected part of graph containing the |
|
|
node. If the graph is not completely connected, this algorithm |
|
|
computes the closeness centrality for each connected part |
|
|
separately. |
|
|
|
|
|
References |
|
|
---------- |
|
|
.. [1] Borgatti, S.P. and Halgin, D. In press. "Analyzing Affiliation |
|
|
Networks". In Carrington, P. and Scott, J. (eds) The Sage Handbook |
|
|
of Social Network Analysis. Sage Publications. |
|
|
https://dx.doi.org/10.4135/9781446294413.n28 |
|
|
""" |
|
|
closeness = {} |
|
|
path_length = nx.single_source_shortest_path_length |
|
|
top = set(nodes) |
|
|
bottom = set(G) - top |
|
|
n = len(top) |
|
|
m = len(bottom) |
|
|
for node in top: |
|
|
sp = dict(path_length(G, node)) |
|
|
totsp = sum(sp.values()) |
|
|
if totsp > 0.0 and len(G) > 1: |
|
|
closeness[node] = (m + 2 * (n - 1)) / totsp |
|
|
if normalized: |
|
|
s = (len(sp) - 1) / (len(G) - 1) |
|
|
closeness[node] *= s |
|
|
else: |
|
|
closeness[node] = 0.0 |
|
|
for node in bottom: |
|
|
sp = dict(path_length(G, node)) |
|
|
totsp = sum(sp.values()) |
|
|
if totsp > 0.0 and len(G) > 1: |
|
|
closeness[node] = (n + 2 * (m - 1)) / totsp |
|
|
if normalized: |
|
|
s = (len(sp) - 1) / (len(G) - 1) |
|
|
closeness[node] *= s |
|
|
else: |
|
|
closeness[node] = 0.0 |
|
|
return closeness |
|
|
|
