0

After checking the documentation on triangles of networkx, I've wondered if there is a more efficient way of generating a triangle free graph than to randomly spawn graphs until a triangle free one happens to emerge, (in particular if one would like to use a constant random seed).

Below is code that spawns graphs until they are triangle free, yet with varying random seeds. For a graph of 10 nodes it already takes roughly 20 seconds.

def create_triangle_free_graph(show_graphs):
    seed = 42
    nr_of_nodes = 10
    probability_of_creating_an_edge = 0.85
    nr_of_triangles = 1  # Initialise at 1 to initiate while loop.
    while nr_of_triangles > 0:
        graph = nx.fast_gnp_random_graph(
            nr_of_nodes, probability_of_creating_an_edge
        )
        triangles = nx.triangles(G).values()
        nr_of_triangles = sum(triangles) / 3
        print(f"nr_of_triangles={nr_of_triangles}")

    return graph

Hence, I would like to ask: Are there faster ways to generate triangle free graphs (using random seeds) in networkx?

a.t.
  • 2,002
  • 3
  • 26
  • 66
  • 1
    Your code only tests if node zero is involved in any triangles, not if there are any triangles at all. – Paul Brodersen Mar 28 '22 at 18:05
  • 1
    For the given edge density (`rho = 0.85`), it is, in fact, impossible to construct a triangle-free graph: https://people.cs.uchicago.edu/~razborov/files/triangles.pdf – Paul Brodersen Mar 28 '22 at 18:07
  • @PaulBrodersen thank you, I believe I have updated the triangle count lines to count all the triangles in the graph. As for the edge density, thank you, I was not aware of that! [The documentation](https://networkx.org/documentation/networkx-1.10/reference/generated/networkx.generators.random_graphs.gnp_random_graph.html) of the `gnp_random_graph` mentions `p` does not equal edge density. It is the probability of creating an edge, which I agree, approaches the edge density. Though (highly) unlikely, it could hence still be possible to generate triangle free graphs with `p=0.85` I think. – a.t. Mar 28 '22 at 18:18

1 Answers1

1

A triangle exists in a graph iff two vertices connected by an edge share one or more neighbours. A triangle-free graph can be expanded by adding edges between nodes that share no neighbours. The empty graph is triangle-free, so there is a straightforward algorithm to create triangle-free graphs.

#!/usr/bin/env python
"""
Create a triangle free graph.
"""

import random
import networkx as nx

from itertools import combinations

def triangle_free_graph(total_nodes):
    """Construct a triangle free graph."""
    nodes = range(total_nodes)
    g = nx.Graph()
    g.add_nodes_from(nodes)
    edge_candidates = list(combinations(nodes, 2))
    random.shuffle(edge_candidates)
    for (u, v) in edge_candidates:
        if not set(n for n in g.neighbors(u)) & set(n for n in g.neighbors(v)):
            g.add_edge(u, v)
    return g

g = triangle_free_graph(10)
print(nx.triangles(g))

The number of edges in the resulting graph is highly dependent on the ordering of edge_candidates. To get a graph with the desired edge density, repeat the process until a graph with equal or higher density is found (and then remove superfluous edges), or until your patience runs out.

cutoff = 0.85
max_iterations = 1e+4
iteration = 0
while nx.density(g) < cutoff:
    g = triangle_free_graph(10)
    iteration += 1
    if iteration == max_iterations:
        import warnings
        warnings.warn("Maximum number of iterations reached!")
        break

# TODO: remove edges until the desired density is achieved
Paul Brodersen
  • 11,221
  • 21
  • 38
  • 1
    A better implementation would check if the desired edge density can be achieved at all using the formula in the paper linked above. – Paul Brodersen Mar 28 '22 at 18:41