Add bipartite normalization for centrality measures (migrated from Trac #528)

[networkx-trac]

Original ticket https://networkx.lanl.gov/trac/ticket/528 Reported 2011-03-25 by @jtorrents, assigned to @hagberg.

Some centrality measures (degree_centrality, betweenness_centrality and closeness_centrality) can be computed for bipartite networks using the same algorithms used for unipartite networks, but we need to adapt the normalization of such measures to the bipartite nature of the network (see reference).

I'm not sure of the best way to implement this feature in NetworkX, I see two main ways to do so: to modify centrality measures to accept the bipartite keyword (and a list of nodes in one bipartite set) or to add a new file to the bipartite module that implements the normalization for the relevant centrality measures.

As a first approximation I've attached an implementation of the second way. The main problem is that closeness_centrality normalizes (and inverts) by default the sum of the shortest paths for each node, so I've added a slightly modified closeness_centrality function to the file attached (with a bipartite input keyword) that returns the raw sum of shortest paths for each node. And then another function does the normalization for bipartite networks.

I've also attached a file that contains a function that returns the southern woman bipartite network (used in the chapter) in order to be able to test my implementation against the results provided by the authors.

Reference:

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

[networkx-trac]

Attachment in Trac by @jtorrents, 2011-03-25: bipartite_centrality.py

[networkx-trac]

Attachment in Trac by @jtorrents, 2011-03-25: davis.py

[networkx-trac]

Comment in Trac by @hagberg, 2011-03-26

I vote for separate functions (like you have implemented).

[networkx-trac]

Attachment in Trac by @hagberg, 2011-03-27: bipartite_centrality.2.py

[networkx-trac]

Attachment in Trac by @hagberg, 2011-03-27: test_bipartite_centrality.py

[networkx-trac]

Comment in Trac by @hagberg, 2011-03-27

Here is an updated version with some simplified logic. It passes the tests you wrote (also attached).

It could use a few more simple tests and documentation.

I haven't read the papers with the algorithms yet but I was wondering about the normalization of closeness centrality if the graph isn't connected. That often causes some confusion in the unipartite case.

[networkx-trac]

Attachment in Trac by @jtorrents, 2011-03-27: bipartite_centrality_3.py

[networkx-trac]

Attachment in Trac by @jtorrents, 2011-03-27: test_bipartite_centrality_3.py

[networkx-trac]

Comment in Trac by @jtorrents, 2011-03-27

Replying to [comment:2 aric]:

Here is an updated version with some simplified logic. It passes the tests you wrote (also attached).

It could use a few more simple tests and documentation.

I've added documentation and more tests. Maybe the documentation is too verbose, it can be simplified. I've tryed to explain in detail the normalization procedure (especially for closeness). I haven't tested that the LaTeX math syntax renders correctly, I have yet to figure out how the documentation system works.

I haven't read the papers with the algorithms yet but I was wondering about the normalization of closeness centrality if the graph isn't connected. That often causes some confusion in the unipartite case.

The paper does not address this issue. In the file attached I've applied the same normalization used in NetworkX for unipartite graphs. I think that it makes sense in the bipartite case too. This normalization makes sure that central nodes in small connected components don't appear very high in the global ranking of nodes by closeness in a big network with a giant connected component (a very common situation in large empirical networks). What do you think?

[networkx-trac]

Comment in Trac by Aric Hagberg <aric.hagberg, 2011-03-28

In [f94fb02c64a8e46162262e70dbfb9c6e78b86a28/networkx]: '''

!CommitTicketReference repository="networkx" revision="f94fb02c64a8e46162262e70dbfb9c6e78b86a28"

Add bipartite centrality measures. Addresses #528 '''

[networkx-trac]

Comment in Trac by @hagberg, 2011-03-28

Thanks for adding the tests and documentation!

I pushed the files into the master repository with your changes and some further modifications of the documentation and some small fixes in the tests.

Please review for errors and completeness.

(We use Sphinx for autogenerating the docs. I need to write a short guide on how to generate them.)

[networkx-trac]

Comment in Trac by @jtorrents, 2011-03-28

Replying to [comment:5 aric]:

Thanks for adding the tests and documentation!

I pushed the files into the master repository with your changes and some further modifications of the documentation and some small fixes in the tests.

Please review for errors and completeness.

I think that with your changes the documentation is now clearer and better organized. The only thing about tests is that, in the setUp function, we create a path_graph(5) that is not actually used in the tests (because you have substituted it for the more convenient path_graph(4)). Do you think that we need more tests for bipartite centrality functions?

(We use Sphinx for autogenerating the docs. I need to write a short guide on how to generate them.)

That guide would be great, but looking at Sphinx's website, it seems that they have good documentation and examples. I'll try to figure out how it works in NetworkX by reading them.

Salut!

[networkx-trac]

Comment in Trac by Aric Hagberg <aric.hagberg, 2011-03-28

In [10e22ba6a953e7c25efc994e394b01bbf742d5f1/networkx]: '''

!CommitTicketReference repository="networkx" revision="10e22ba6a953e7c25efc994e394b01bbf742d5f1"

Remove unused graph in test setup. Addresses #528 '''

[networkx-trac]

Comment in Trac by @jtorrents, 2011-04-14

Aric,

Do you think that something else needs to be done for this ticket? If not, I think that we should close it and set it to fixed.

Salut!

[networkx-trac]

Comment in Trac by @hagberg, 2011-04-14