2
\$\begingroup\$

Given a directed graph G of 20+ million edges and approximately 2 million unique nodes, can this function/process be made faster on a dataset of 40k edges?

The current speed is at ~1.8 seconds per edge.

import pandas as pd
import networkx as nx

# main feature calculator
def jacard_inbound(u,v):
    preds = G.predecessors(v)
    result = [jacard_coef(u,x) for x in preds]
    return sum(result), max(result), sum(result)/len(result)


# jacquard's coefficient & helper functions
def jacard_coef(u,v):
    return common_friends(u,v)/total_friends(u,v)

def total_friends(u,v):
    return len(set(Gamma(u)).union(Gamma(v)))

def common_friends(u,v):
    return len(set(Gamma(u)).intersection(Gamma(v)))

# to cache calculated results
gamma_dict = dict()   
def Gamma(u):
    s = gamma_dict.get(u)
    if s is None:
        s = set(G.successors(u)).union(G.predecessors(u))
        gamma_dict[u]=s
    return s

Running example:

# sample graph
G = nx.DiGraph()
G.add_edges_from([(1,2), (1,3), (2,3), (3,4), (3,5), (7,1), (5,6), (8,2), (9,0)])

# sample edges
dataset = pd.DataFrame(columns = ['source','target'])
dataset['target'] = [3, 6, 2, 3]
dataset['source'] = [2, 1, 8, 1] 

t = time.time()
dataset['jacard_inbound'] = dataset[['source','target']].apply(lambda x: jacard_inbound(x['source'],x['target']), axis=1)
print(time.time() - t)
\$\endgroup\$
  • \$\begingroup\$ Can you explain what the program is supposed to do? \$\endgroup\$ – Gareth Rees Sep 4 '18 at 8:10
  • \$\begingroup\$ @GarethRees to compute the inbound Jacard Coefficient sum, maximum and average for each edge. It basically computes a ratio of the amount of common neighbors between the source node and the nodes that follow the target. \$\endgroup\$ – Nal Sep 4 '18 at 9:39
  • \$\begingroup\$ The example does not work for me since it does not define the graph G. \$\endgroup\$ – Gareth Rees Sep 5 '18 at 7:25
  • \$\begingroup\$ @GarethRees I updated the example. \$\endgroup\$ – Nal Sep 5 '18 at 7:33
1
\$\begingroup\$
  1. "Jaccard coefficient", not "Jacard" or "Jacquard": it's named after Paul Jaccard.

  2. There are no docstrings. What do these functions do? What do they return?

  3. The results of these functions depend on the global variable G. If you ever needed to generalize your program to operate on more than one graph at a time this dependency would become very inconvenient. The functions ought to either take the graph as an argument, or be methods on the graph class.

  4. Is Gamma standard graph terminology for this function? I've seen it called 'neighbourhood' (or 'open neighbourhood' when it needs to be clear that u is not included).

  5. Python has a built-in decorator functools.lru_cache for caching the results of a function. So you can write:

    @lru_cache(maxsize=None)
    def neighbourhood(g, u):
        "Return the set of vertices in the graph g that are adjacent to u."
        return set(g.successors(u)).union(g.predecessors(u))
    
  6. Reuse the set of successors instead of discarding it:

    @lru_cache(maxsize=None)
    def neighbourhood(g, u):
        "Return the set of vertices in the graph g that are adjacent to u."
        result = set(g.successors(u))
        result.update(g.predecessors(u))
        return result
    
  7. In common_friends and total_friends, there is no need to make a copy of the neighbourhood before taking the union/intersection. You can take the union/intersection directly:

    def total_friends(g, u, v):
        """Return the number of vertices in the graph g that are in the
        neighbourhoods of u or v (or both).
    
        """
        return len(neighbourhood(g, u) | neighbourhood(g, v))
    
    def common_friends(g, u, v):
        """Return the number of vertices in the graph g that are in the
        neighbourhoods of both u and v.
    
        """
        return len(neighbourhood(g, u) & neighbourhood(g, v))
    
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.