Improving the performance of triangles

Author: zephyr111Created Jan 3, 2022Updated May 24, 2026

Labelstype: EnhancementsNeeds PR

Hello everyone,

Based on this StackOverflow post, we have found that triangles of NetworkX is a bit slow and can be improved (assuming a higher memory footprint is acceptable).

For non-directed graph, the following code can be used:

python

def triangles(G):
    nodeNeighbours = {
        # The filtering of the set ensure each triangle is only computed once
        node: set(n for n in edgeInfos.keys() if n > node)
        for node, edgeInfos in G.adjacency()
    }
    
    res = {node: 0 for node in G.nodes()}
    
    for node1, neighbours in nodeNeighbours.items():
        for node2 in neighbours:
            for node3 in neighbours & nodeNeighbours[node2]:
                # Dispatch the counts to each node participating to the triangle found
                res[node1] += 1
                res[node2] += 1
                res[node3] += 1

    return res

This code is significantly faster big graphs.

For directed graphs, one need to compute the incoming edges of each nodes. This can be computed using a dictionary and a basic walk on the full graph (similar to what is done with nodeNeighbours).

Is this acceptable to use this implementation to improve the existing code?

Thank you.

Steps to Reproduce

Here is an example to test the performance of triangles:

python

import networkx as nx
# For bigger tests (slow):  G = nx.erdos_renyi_graph(15000, 0.005)
G = nx.erdos_renyi_graph(1000, 0.1)
res1 = nx.triangles(G)
res2 = triangles(G)
assert res1 == res2

Environment

Python version: 3.9.9 NetworkX version: 2.6.3

Source: networkx/networkx

View original on GitHub View discussion on GitHub