Bipartite (two-mode) networks are ubiquitous. When calculating node centrality measures in bipartite networks, a common approach is to apply PageRank on the one-mode projection of the network. However, the projection can cause information loss and distort the network topology. For better node ranking on bipartite networks, it is preferable to use a ranking algorithm that fully accounts for the topology of both modes of the network.
We present the BiRank package, which implements bipartite ranking algorithms HITS, CoHITS, BGRM, and BiRank. BiRank provides convenience options for incorporating node-level weights into rank estimations, allowing maximum flexibility for different purpose. It can efficiently handle networks with millions of nodes on a single midrange server. Both R and Python versions are available.
CRAN package with highly efficient functions for estimating various rank (centrality) measures of nodes in bipartite graphs (two-mode networks) including HITS, CoHITS, BGRM, and BiRank. Also provides easy-to-use tools for incorporating or removing edge-weights during rank estimation, projecting two-mode graphs to one-mode, efficiently estimating PageRank in one-mode graphs, and for converting edgelists and matrices to sparseMatrix format. Best of all, the package's rank estimators can work directly with common formats of network data including edgelists (class data.frame
, data.table
, or tbl_df
) and adjacency matrices (class matrix
or dgCMatrix
).
This package can be directly installed via CRAN with install.packages("birankr")
. Alternatively, newest versions of this package can be installed with devtools::install_github("BrianAronson/birankr")
Let's pretend we have a dataset (df
) containing patient-provider ties (patient_id
and provider_id
) among providers that have ever prescribed an opioid:
df <- data.frame(
patient_id = sample(x = 1:10000, size = 10000, replace = T),
provider_id = sample(x = 1:5000, size = 10000, replace = T)
)
We are interested in identifying patients who are likely doctor shopping. We assume that a highly central patient in the patient-doctor network is likely to be a person who is deliberately identifying more "generous" opioid prescribers. We therefore estimate a patients' rank in this network with the CoHITS algorithm:
df.rank <- br_cohits(data = df)
Note that rank estimates are scaled according to the size of the network, with more nodes tending to result in smaller ranks. Due to this, it is often advisable to rescale rank estimates more interpretable numbers. For example, we could rescale such that the mean rank = 1 with the following data.table syntax:
df.rank <- data.table(df.rank)
df.rank[, rank := rank/mean(rank)]
Finally, we decide to identify the IDs and ranks of the highest ranking patients in df
:
head(df.rank[order(rank, decreasing = T), ], 10)
For a more detailed example, check out examples/Marvel_social_network.md, where we use the ranking algorithm to analyze the Marvel comic book social network.
Below is a brief outline of each function in this package:
- bipartite_rank
- Estimates any type of bipartite rank.
- br_bgrm
- Estimates ranks with BGRM algorithm
- br_birank
- Estimates ranks with BiRank algorithm
- br_cohits
- Estimates ranks with CoHITS algorithm
- br_hits
- Estimates ranks with HITS algorithm
- pagerank
- Estimates ranks with PageRank algorithm
- project_to_one_mode
- Creates a one mode projection of a sparse matrix
- sparsematrix_from_edgelist
- Creates a sparsematrix from an edgelist
- sparsematrix_from_matrix
- Creates a sparsematrix from a matrix
- sparsematrix_rm_weights
- Removes edge weights from a sparsematrix
Full documentation of birankr
can be found in birankr.pdf.
To run the unit tests, install the birankr and devtools packages and run:
devtools::test("birankr")
- Nov.10, 2021 (v1.0.1): drop support for python3.5; add support for python3.9
birankpy
provides functions for estimating various rank measures of nodes in bipartite networks including HITS, CoHITS, BGRM, and BiRank.
It can also project two-mode networks to one-mode, and estimate PageRank on it.
birankpy
allows user-defined edge weights.
Implemented with sparse matrix, it's highly efficient.
networkx
pandas
numpy
scipy
Install with pip
:
pip install birankpy
Let's pretend we have an edge list edgelist_df
containing ties between top nodes and bottom nodes:
top_node | bottom_node |
---|---|
1 | a |
1 | b |
2 | a |
... | .. |
123 | z |
To performing BiRank on this bipartite network, just:
bn = birankpy.BipartiteNetwork()
bn.set_edgelist(edgelist_df, top_col='top_node', bottom_col='bottom_node')
top_birank_df, bottom_birank_df = bn.generate_birank()
For a more detailed example, check out examples/Marvel_social_network.ipynb, where we use the ranking algorithm to analyze the Marvel comic book social network.
See documentation for birankpy
at birankpy doc.
To run the unit tests, first go to the tests
directory and then run:
python test_birankpy.py
In general, you can contribute to this project by creating issues. You are also welcome to contribute to the source code directly by forking the project, modifying the code, and creating pull requests. If you are not familiar with pull requests, check out this post. Please use clear and organized descriptions when creating issues and pull requests.
You can use issues to report bugs and seek support. Before creating any new issues, please check for similar ones in the issue list first.