bipartite network Degree-preserving randomization with constraints

user_15550604 0
Viewed 90

I am working on a sample data containing several papers, the topics they belong to, and the publication years of those papers, it looks like this:

paper_id topic pub_year
2031361154 0 1998
2088633475 1 1995
1987003396 2 1995
2246118404 3 1992
2017547909 1 1996
2032449907 4 1993
2053684599 0 1991
1968369145 1 1997
2160198778 4 1997
2026639487 3 1991

I am trying to reshuffle the publication years of those papers (keep the number of papers in each topic and published in each year constant) as preparation for a null model. If without constraints, this can be done simples by np.random.permutation. An example table after reshuffling the publication year is like this:

paper_id topic reshuffled_pub_year
2031361154 0 1998
2088633475 1 1997
1987003396 2 1995
2246118404 3 1992
2017547909 1 1996
2032449907 4 1993
2053684599 0 1991
1968369145 1 1997
2160198778 4 1995
2026639487 3 1991

But I want to ensure that the reshuffled years of those papers stay inside the period of the corresponding topics. For example, in the first table, there are papers about topic 1 published only in 1995, 1996, and 1997, so the reshuffled years of all papers about topic 1 stay the period from 1995 to 1997. Similarly, topic 0 in [1991,1998], topic 2 in [1995], topic 3 in [1991,1992] and topic 4 in [1993,1997]. But in the second table, the reshuffled publication year of paper 2246118404 is 1998, as this paper is about topic 3, the year can only be 1991 or 1992. So I need to specify the constraints during the reshuffle.

I have searched web pages and papers about this, I think this question can be modeled as a bipartite network degree-preserving randomization with constraints. The two node types in this bipartite network are topic and pub_year and an example network is given as the following figure:

example network

To reshuffle the links in this bipartite network, I tried configuration_model in networkx using python. So I can guarantee the degrees of topics and years (But this is not different from np.random.permutation?). But as far as I know, configuration_model does not accept any constraint. In this example, tp1 has links to y1 and y2. So, in a desired reshuffled network, tp1 cannot have links to y3 and y4. Similarly, no links between (tp2,y4), (tp3,y1/y3), (tp4,y1/y2).

I would like to know if I am going in the right direction, i.e., modeling this task as a bipartite network reshuffle problem. If so, is there any tool that I can use for this task?

randomized-algorithm bipartite networkx python
1 Answers

A simple script to do the yaer shuffling:

import random

# replace it with your data
papers = [
    {"paper_id": 2031361154, "topic": 0, "year": 1998},
    {"paper_id": 2088633475, "topic": 1, "year": 1995},
    {"paper_id": 1987003396, "topic": 2, "year": 1995},
    {"paper_id": 2246118404, "topic": 3, "year": 1992},
    {"paper_id": 2017547909, "topic": 1, "year": 1996},
    {"paper_id": 2032449907, "topic": 4, "year": 1993},
    {"paper_id": 2053684599, "topic": 0, "year": 1991},
    {"paper_id": 1968369145, "topic": 1, "year": 1997},
    {"paper_id": 2160198778, "topic": 4, "year": 1997},
    {"paper_id": 2026639487, "topic": 3, "year": 1991}
]

topicRanges = {}
for paper in papers:
    topic = paper["topic"]
    if topic in topicRanges:
        topicRanges[topic] = {
            "min": min(paper["year"], topicRanges[topic]["min"]),
            "max": max(paper["year"], topicRanges[topic]["max"])
        }
    else:
        topicRanges[topic] = {"min": paper["year"], "max": paper["year"]}

shuffled = []
for paper in papers:
    topic = paper["topic"]
    topicRange = topicRanges[topic]
    year = random.randint(topicRange["min"], topicRange["max"])
    shuffled.append(
        {"paper_id": paper["paper_id"], "topic": topic, "year": year})

print(shuffled)
user_107564890
Related