[Python] Coeff Clust DiGraph()

[Andrealeo92]

Ciao a tutti!
Sto provando a calcolare il coeffciente di clustering per ogni singolo nodo di un DiGraph() utilizzando la libreria networkx ma mi sono resa conto che non tutti i valori sono corretti.

Ho trovato diversi algoritmi di codice alternativo sul web che segue la strada del calcolo secondo i Neighbors ma anche questo non torna per tutti i nodi.

Potreste aiutarmi? Cosa mi consigliate?

Ho provato anche la strada del calcolo secondo i Triangoli anche se essendo un DiGraph() debolmente connesso non trovo riscontro.

Grazie

[apatriarca]

Senza sapere nulla del tuo codice o del particolare esempio testato è difficile dire qualcosa a riguardo. Sinceramente credo che tu abbia definito un grafo diverso da quello che ti aspetti o che il risultato che ti aspetti non è quello corretto se tutti i metodi che hai provato restituiscono qualcosa di diverso.

[Andrealeo92]

Grazie per la risposta.
Il Grafo mi pare sia costruito bene anche perchè il betweenneess_centrality e il closeness_centrality (seguendo le indicazioni per il DiGraph ) tornano correttamente.

Il coeff di clustering NO, almeno utilizzando la libreria nx.clustering(DiGraph())

Ho provato a controllare se ci fosse qualche parametro ma nulla, perchè nel caso del closeness ho dovuto invertire il grafo e attivare un parametro in questo modo:

Codice:


# Le info del file le ho inserite in un pd.DataFrame
M_D = nx.MultiDiGraph()
[M_D.add_edge(df[0][i], df[2][i], label= df[1][i]) for i in range(len(df)]   
D = nx.DiGraph(M_D)

nx.closeness_centrality(D.reverse(), wf_improved=False)  # torna correttamente
# (il parametro wf_improved è di Default True per i Grafi Non Orientati = nx.Graph() )
# wf_improved=False per i Grafi Orientati = nx.DiGraph()

nx.clustering(D) # tornano solo alcuni valori
Per questa funzione non ho trovato parametri significativi boh


Ho poi trovato codice sul web :

Codice:

C = dict()
for node in n:
     neighbours=[n_ for n_ in nx.neighbors(D, node)]
     n_neighbors=len(neighbours)
     n_links=0
     if n_neighbors>1:
          for node1 in neighbours:
               for node2 in neighbours:
                   if D.has_edge(node1, node2):
                        n_links+=1
           n_links/=2 #because n_links is calculated twice
           clustering_coefficient = n_links/(0.5*n_neighbors*(n_neighbors-1))
      else:
           clustering_coefficient = 0.0
     C[node] = (clustering_coefficient)


Mi restituisce valori diversi dal sia da quelli attesi che da quelli calcolati con la funzione di libreria. Boh
Ho trovato anche questo:

Codice:

clusteringDict = dict()
for node in G.nodes():
    neighboursOfNode = []
    nodesWithMutualFriends = []
        # store all neighbors of the node in an array so we can compare
    for neighbour in G.neighbors(node):
        neighboursOfNode.append(neighbour)
    for neighbour in G.neighbors(node):
        for second_layer_neighbour in G.neighbors(neighbour):
                # compare if any second degree neighbour is also a first degree neighbour (this makes a triangle)
                # if so, append it to the mutual friends list
            if second_layer_neighbour in neighboursOfNode:
                nodesWithMutualFriends.append(second_layer_neighbour)
        # filter duplicates from the mutual friend array
    nodesWithMutualFriends = list(nodesWithMutualFriends) #set
    clusteringCoefficientOfNode = 0
        # apply coefficient formula to calculate
    if len(nodesWithMutualFriends):
        A = float(len(nodesWithMutualFriends))
        B = len(G.neighbors(node))
        C = (B - 1)
        clusteringCoefficientOfNode = A/(B*C)
    clusteringDict[node] = (clusteringCoefficientOfNode)



Valori diversi anche tra questi due codici.

Con la funzione di libreria nc.clustering() il valore come un 0.59..(atteso) viene calcolato dalla funzione come 0.611111. Un 0.051 (corretto) invece come 0.076

Grazie

[Andrealeo92]

Ho provato a calcolare i triangoli per un Graph() e sto notando che per nodi con lo stesso numero di triangoli, il coefficiente di clustering è lo stesso. Ora però non so come calcolare le triples() per ciascun nodo.

Magari seguendo questa strada riesco ad arrivarci....? Grazie

[Andrealeo92]

Ciao, Su wikipedia dice che il coeffic di clustering di ciascun nodo nel caso di grafi orientati è dato dal numero dei neighbors di ogni nodo / k(k-1) dove k è il numero di edges dei neighbors.

Trovato il numero dei neighbors per ogni nodo.
Come calcolo il numero k degli edges di ciascun neighbors?

Sto seguendo più strade. Sono corrette? Grz

[Andrealeo92]

Perdonate mi correggo:
Ho fatto la prova considerando il Grafo Non Orientato (G) e il coeff clust locale per singolo nodo viene calcolato come:
2*(num triangles del nodo) / ( len(list(G.neighbors(node)))*(len(list(G.neighbors(node)))-1) )
I valori tornano correttamente!!!

Nel caso del Grafo Orientato (D), il coeff clust per singolo nodo viene calcolato come:
(num triangles del nodo) / ( len(list(D.neighbors(node)))*(len(list(D.neighbors(node)))-1) )

L'unico problemino è che nx.triangles() per un grafo Diretto non funziona.

Come posso calcolare il numero di triangoli per ciascun nodo? esiste un modo? Grazie