Is it possible to have less dyads then triangles in a graph?

[Thomas Selleslagh]

I don't really know where to post this question but I am analyzing a graph and I do not understand my results. I suspect something to be wrong with either my code or with my interpretation of the output.

So, I have a graph constructed in Python using NetworkX. I am examining homophily within the network. Therefore I want to analyse the clustering, dyads, etc.

I need to count the number of triangles. As such I use the 'nx.triangles' function and compute this with the following code:

triangles = sum(nx.triangles(G).values()) // 3

I also want to know the number of dyads (connected pairs of nodes). I do this with the following code:

def count_dyads(G): dyad_count = 0

for node in G: neighbors = set(G.neighbors(node)) for neighbor in neighbors: dyad_count += 1 return dyad_count

I understand that each pair is counted twice so I divide the dyad count by 2 to get the number of connected pairs.

What I don't understand I how it is possible that I find that there are more triangles than dyads, as every triangle consists of three dyads? I find 1,325,215 triangles but only 189,464 dyads (this is even before dividing the number of dyads by 2).

Can someone elaborate as to what my mistake is or how my understanding of these concepts is wrong?

Thanks and a happy New year!

[Aditi Juneja]

Hi, I don't think there are any errors in the way you are computing the number of triangles and the number of connected pairs of nodes(which can be computed like this also, dyad_count = G.number_of_edges()). Even if you have self-loops or multiple edges the count of edges should be more than the triangles because nx.triangles ignores self loops and treats multiple edges between 2 nodes as same.

import networkx as nx

G=nx.complete_graph(4)

G=nx.MultiGraph(G)

G.add_edges_from([(0,1),(2,0),(1,2),(0,0)])

print(G.number_of_edges())

print(sum(nx.triangles(G).values()) // 3)

10 4

Could you pls tell more about the graph's structure?

Thank you

[Dan Schult]

Counting is often very unintuitive. It turns out that the number of triangles is often much larger than the number of edges (Dyads). It’s often helpful to think of a simple scalable example network structure to work through the numbers. Here I suggest the complete graph on n nodes.  It has n*(n-1)/2 edges.  And it has n*(n-1)*(n-2)/6 triangles. So the number of edges increases like n^2 while the number of triangles goes up like n^3.  Of course other structures have different behaviors. So a lot depends on your network. The densest networks will have more triangles, while sparse networks may have no triangles at all (like a path graph).

;)

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/cd33a35e-d0ad-4fce-86f7-7d9c539490c3n%40googlegroups.com.