| #-*- coding: utf-8 -*- |
| # Copyright (C) 2011 by |
| # Jordi Torrents <jtorrents@milnou.net> |
| # Aric Hagberg <hagberg@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| import networkx as nx |
| __author__ = """\n""".join(['Jordi Torrents <jtorrents@milnou.net>', |
| 'Aric Hagberg (hagberg@lanl.gov)']) |
| __all__=['degree_centrality', |
| 'betweenness_centrality', |
| 'closeness_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. |
| |
| See Also |
| -------- |
| betweenness_centrality, |
| closeness_centrality, |
| sets, |
| is_bipartite |
| |
| Notes |
| ----- |
| The nodes input parameter must conatin all nodes in one bipartite node set, |
| but the dictionary returned contains all nodes from both bipartite node |
| sets. |
| |
| 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. |
| http://www.steveborgatti.com/papers/bhaffiliations.pdf |
| """ |
| top = set(nodes) |
| bottom = set(G) - top |
| s = 1.0/len(bottom) |
| centrality = dict((n,d*s) for n,d in G.degree_iter(top)) |
| s = 1.0/len(top) |
| centrality.update(dict((n,d*s) for n,d in G.degree_iter(bottom))) |
| return 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. |
| |
| See Also |
| -------- |
| degree_centrality, |
| closeness_centrality, |
| sets, |
| 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. |
| |
| 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. |
| http://www.steveborgatti.com/papers/bhaffiliations.pdf |
| """ |
| top = set(nodes) |
| bottom = set(G) - top |
| n = float(len(top)) |
| m = float(len(bottom)) |
| s = (n-1) // m |
| t = (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 = (m-1) // n |
| r = (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 |
| |
| 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. |
| |
| See Also |
| -------- |
| betweenness_centrality, |
| degree_centrality |
| sets, |
| is_bipartite |
| |
| Notes |
| ----- |
| The nodes input parameter must conatin all nodes in one bipartite node set, |
| but the dictionary returned contains all nodes from both node sets. |
| |
| 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. |
| http://www.steveborgatti.com/papers/bhaffiliations.pdf |
| """ |
| closeness={} |
| path_length=nx.single_source_shortest_path_length |
| top = set(nodes) |
| bottom = set(G) - top |
| n = float(len(top)) |
| m = float(len(bottom)) |
| for node in top: |
| sp=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.0) / ( len(G) - 1 ) |
| closeness[node] *= s |
| else: |
| closeness[n]=0.0 |
| for node in bottom: |
| sp=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.0) / ( len(G) - 1 ) |
| closeness[node] *= s |
| else: |
| closeness[n]=0.0 |
| return closeness |
| |
