CODEWITHSUNDEEP
pythonigraph
Mrye
Mrye

Reputation: 727

Python Igraph : Finding number of triangles for each vertex

How can I find the number of triangles for vertices in a graph ?

Let say I have a graph g. I can calculate the degree for each vertex using this command

g.vs.degree()

It will return a list of numbers. Is there any similar method to count the number of triangles that will return a list ?

Previously I can calculate using Gephi, but now I'm shifted to igraph.

Update 1

By using cliques, i will get something like this

import igraph as ig
g = ig.Graph.Famous('Krackhardt_Kite')
g.cliques(min=3,max=3)

[(0, 1, 3),
 (0, 2, 3),
 (0, 2, 5),
 (0, 3, 5),
 (1, 3, 4),
 (1, 3, 6),
 (1, 4, 6),
 (2, 3, 5),
 (3, 4, 6),
 (3, 5, 6),
 (5, 6, 7)]

So the number of triangles should be return like this (based on Gephi)

[4,4,3,8,3,5,5,1,0]

So does igraph provide these function to calculate the number of triangles ?

Upvotes: 2

Views: 1627

Answers (1)

Tamás
Tamás

Reputation: 48051

Probably not the most efficient, but this will work:

def triangles(g):
    cliques = g.cliques(min=3, max=3)
    result = [0] * g.vcount()
    for i, j, k in cliques:
        result[i] += 1
        result[j] += 1
        result[k] += 1
    return result

Another variant which does not use cliques():

from itertools import combinations

def triangles(g):
    result = [0] * g.vcount()
    adjlist = [set(neis) for neis in g.get_adjlist()]
    for vertex, neis in enumerate(adjlist):
        for nei1, nei2 in combinations(neis, 2):
            if nei1 in adjlist[nei2]:
                result[vertex] += 1
    return result

I haven't done any benchmarks so this one might be faster or slower than the previous one - I have no idea.

Upvotes: 2

Related Questions