generate_triadic_closure

graph_tool.generation.generate_triadic_closure(g, t, probs=True, curr=None, ego=None)

Closes open triads in a graph, according to an ego-based process.

Parameters:

gGraph

Graph to be modified.

tVertexPropertyMap or scalar

Vertex property map (or scalar value) with the ego closure propensities for every node.

probsboolean (optional, default: True)

If True, the values of t will be interpreted as the independent probability of connecting two neighbors of the respective vertex. Otherwise, it will determine the integer number of pairs of neighbors that will be closed.

currEdgePropertyMap (optional, default: None)

If given, this should be a boolean-valued edge property map, such that triads will only be closed if they contain at least one edge marged with the value True.

egoEdgePropertyMap (optional, default: None)

If given, this should be an integer-valued edge property map, containing the ego vertex for each closed triad, which will be updated with the new generation.

Returns:

egoEdgePropertyMap

Integer-valued edge property map, containing the ego vertex for each closed triad. A value of -1 marks original edges that were not created by triadic closure.

Notes

This algorithm [peixoto-disentangling-2022] consist in, for each node u, connecting all its neighbors with probability given by t[u]. In case probs == False, then t[u] indicates the number of random pairs of neighbors of u that are connected. This algorithm may generate parallel edges.

This algorithm has a complexity of \(O(N\left<k^2\right>)\), where \(\left<k^2\right>\) is the second moment of the degree distribution.

References

[peixoto-disentangling-2022]

Tiago P. Peixoto, “Disentangling homophily, community structure and triadic closure in networks”, Phys. Rev. X 12, 011004 (2022), DOI: 10.1103/PhysRevX.12.011004 [sci-hub, @tor], arXiv: 2101.02510

Examples

>>> g = gt.collection.data["karate"].copy()
>>> gt.generate_triadic_closure(g, .5)
<...>
>>> gt.graph_draw(g, g.vp.pos, output="karate-triadic.png")
<...>

Karate club network with added random triadic closure edges.