2
\$\begingroup\$

I have a pretty big file (3 million lines) with each line being a person-to-event relationship. Ultimate, I want to project this bipartite network onto a single-mode, weighted, network, and write it to a CSV file. I'm using NetworkX, and I've tested my code on smaller sample datasets, and it works as it should. However, I need to scale this code up to handle my actual dataset, so I need my code to be as efficent as possible and not just maxes out on memory and spins and spin on this last step like it currently does.

I'm using an AWS EC2 machine with 64GB of memory.

After some sample testing, I've realized that things are getting hung up on the second to last step where the bipartite graph (user-to-event) is being projected into a single-mode (user-to-user, based on shared event) graph.

More information about the original data: Some events have only 1 person attending them, while other events have 5,000 people attending them. Because of this, there will be a huge number of edges (I predict ~50M) created when the bipartite network is folded onto a single-mode network.

In order to hopefully speed things up, I've altered to source code of NetworkX's weighted_projected_graph function to not write the projected graph to a new graph as it typically is done, but instead write those edges to a list, and then write that list to CSV with Pandas.

I'm sure there are other ways to speed up the projection portion of this code.

Code using NetworkX to Project Bipartite Network and Pandas to Write the File:

# import modules
import time
import csv
import networkx as nx
from networkx.algorithms import bipartite
import datetime 
import pandas as pd

startTime = datetime.datetime.now()

# rename files
infile = 'release-youtube-links.csv'
name_outfile_pd = infile.replace('.csv', '_nameFolded_pd.csv.')
print 'Files renamed at: ' + str(datetime.datetime.now() - startTime)

# load CSV into a dict
with open(infile, 'rb') as csv_file:
    rawData = list(csv.DictReader(csv_file))
    print 'Files loaded at: ' + str(datetime.datetime.now() - startTime)

for i in rawData:
    i['Name'] = 'Name:' + i['Name']
    i['Event'] = 'Event:' + i['Event']

# create edgelist for Name -x- Event relationships
edgelist = []
for i in rawData:
    edgelist.append(
    (i['Event'],
     i['Name'])    
    )
print 'Bipartite edgelist created at: ' + str(datetime.datetime.now() - startTime)

# deduplicate edgelist
edgelist = sorted(set(edgelist))
print 'Bipartite edgelist deduplicated at: ' + str(datetime.datetime.now() - startTime)

# create a unique list of Name and Event for nodes
Event = sorted(set([i['Event'] for i in rawData]))
Name = sorted(set([i['Name'] for i in rawData]))
print 'Node entities deduplicated at: ' + str(datetime.datetime.now() - startTime)

# add nodes and edges to a graph
B = nx.Graph()
B.add_nodes_from(Event, bipartite=0)
B.add_nodes_from(Name, bipartite=1)
B.add_edges_from(edgelist)
print 'Bipartite graph created at: ' + str(datetime.datetime.now() - startTime)

# create bipartite projection graph
name_nodes, event_nodes = bipartite.sets(B)
event_nodes = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
name_nodes = set(B) - event_nodes

# project graph and write projected graph's edgelist to a list
if B.is_multigraph():
    raise nx.NetworkXError("not defined for multigraphs")
if B.is_directed():
    pred = B.pred
else:
    pred = B.adj
    G = nx.Graph()
G.graph.update(B.graph)
G.add_nodes_from((n,B.node[n]) for n in name_nodes)
n_top = float(len(B) - len(name_nodes))
folded = []
for u in name_nodes:
    unbrs = set(B[u])
    nbrs2 = set((n for nbr in unbrs for n in B[nbr])) - set([u])
    for v in nbrs2:
        vnbrs = set(pred[v])
        common = unbrs & vnbrs
        weight = len(common)
        row = u, v, weight
        folded.append(row)

# write projected graph list to CSV
df = pd.DataFrame(folded)
df.to_csv(name_outfile_pd)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.