User Tools

Site Tools


chicoutimi_2016:simmelian_backbone_de_bobo_nick

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / Session by session cutdown

Simmelian backbone de Bobo Nick

Cette approche développée par Bobo Nick permet de filtrer les arêtes d'un graphe qui s'avère trop dense (comme sur la figure), pour en extraire le squelette.

Le graphe de la figure est celui utilisé par Bobo Nick et représentant les liens d'amitiés facebook d'étudiants d'une université de Chicago. Les couleurs sont attribués aux sommets selon l'appartenance à des “fraternités” étudiantes. Il compte 769 sommets et 33312 arêtes (soit plus de 40 fois plus).

L'approche repose sur deux ingrédients:

  • La force des arêtes (incidentes à un sommet ), qui permet ensuite de les ordonner (localement, toujours par rapport à un sommet ).
  • La redondance des arêtes.

Ces deux notions s'appuient sur la structure de triade: un triangle dans un graphe, un cycle de longueur 3. Dans un triangle, un sommet est toujours un voisin commun des deux autres sommets. C'est cette structure qui est à la base des phénomènes “petit monde” au coeur de la théorie des réseaux du même nom. Cette notion a été abondamment discutée et étudiée dans des travaux de sociologie, notamment dans l'article original de Granovetter.

  • Granovetter, M. S. (1973). “The Strength of Weak Ties.” The American Journal of Sociology 78(6): 1360-1380.

La figure montre le squelette du graphe extrait selon la méthode de Bobo Nick. On observe la prédominance des liens d'amitiés entre des membres d'une même fraternité. Ce sous-graphe comporte 570 sommets et 9620 arêtes. Certains sommets ont été écartés (il faudrait envisagé de les raccrocher au squelette), soit parce qu'ils sont isolés, soit parce qu'ils forment avec d'autres sommets un petit groupe qui n'apparait pas ici.

Force

Nick considère deux cas pour définir la force des arêtes:

  • Soit les données sont équipées d'une valeur (sur les arêtes) permettant de juger de leur force (de leur importance, de leur position, etc.).
    • C'est le cas, par exemple, si les sommets sont équipées d'une similarités (ou d'une dissimilarités), ou de la valeur de similarités ayant donné naissance au graphe. Une arête forte est une arête avec une forte valeur de similarité.
  • Soit nous ne disposons que de la topologie du graphe (les liens). On peut alors calculer pour chaque arête, le nombre de triangles qui la contiennent.
    • Cela se calcule facilement. Si , alors la force de est le nombre de voisins communs à et , c'est-à-dire .

Cette force des arêtes permet ensuite d'ordonner les arêtes incidentes à un sommet : est l'arête la plus forte, puis viennent

Redondance

C'est le paramètre important du modèle, qui permet d'aller chercher les arêtes du squelette.

En deux mots, la redondance s'intéresse aux sommets incidents à une arête . L'arête qui lient et est redondante si et ont une vision similaire de l'importance relative des voisins qu'ils ont en commun.

  • Nick propose une première approche où l'on fixe un paramètre pour déterminer les arêtes incidents à (et à ) les plus fortes: et . On considère les voisins de et de attachés à ces arêtes et .

La redondance de l'arête peut alors être définie comme le nombre de voisins communs à et à parmi ces sommets les plus forts, c'est-à-dire

  • Le choix du paramètre peut s'avérer toutefois difficile. Bobo Nick propose une deuxième approche qui évite de fixer . Il propose de faire varier (en le bornant peut-être par une valeur maximale ) et de trouver la redondance maximale parmi toutes les valeurs de possibles. La taille des ensembles qui sont considérés étant variable, Nick propose de normaliser les valeurs calculés en fonction du nombre de sommets considérés:

La mesure ainsi définie est connue par ailleurs, c'est la mesure de Jaccard introduite en 1910 dans le contexte de la classification d'espèces florales des massifs de Haute-Savoie.

  • Jaccard, P. (1901). “Distribution de la flore alpine dans la Bassin de Dranses et dans quelques régions voisines.” Bulletin de la Société Vaudoise des Sciences Naturelles 37: 241–272.
L'algorithme
  • On calcule la force des arêtes
  • On ordonne, pour chaque sommet, la liste de ses arêtes incidentes
  • On se donne donc une valeur maximale pour évaluer la redondance, que l'on calcule
  • On fixe un seuil pour filtrer les arêtes (en fonction de leur redondance)
    • On écarte les arêtes dont la redondance est inférieure à
SImmelian.py
from tulip import *
from numpy import *
 
class Simmelian(object):
    '''
    computes the Simmelian backbone of a non-directed graph according to Bobo Nick's approach:
    Nick, B., C. Lee, et al. (2013). Simmelian Backbones: Amplifying Hidden Homophily in Facebook Networks.
    Advances in Social Network Analysis and Mining (ASONAM).
 
    Implements the non parametric version of edge redundancy (see paper for details).
 
    Uses an optional double property argument (that stores edge strength).
    '''
    def __init__(self, graph, strength_name_property=None):
        super(Simmelian, self).__init__()
        self.graph = graph
        self.strength_name_property = strength_name_property
        self.ranked_edges = {}
        self.rank_edges()
        self.edge_redundancy = self.graph.getDoubleProperty('edge_redundancy')
 
    def compute_edge_strength(self, node):
        '''
        computes edge strength, if no double property is assigned
        edges are those incident to node
        (edge strength is not defined globally but locally to nodes)
        (see Bobo Nick's paper for details)
        '''
        if self.strength_name_property != None:
            self.edge_strength = self.graph.getDoubleProperty(self.strength_name_property)
            return
        self.strength_name_property = 'edge_strength'
        self.edge_strength = self.graph.getDoubleProperty(self.strength_name_property)
        for e in self.graph.getInOutEdges(node):
            ego = self.graph.source(e)
            alter = self.graph.target(e)
            ego_neighs = self.graph.getInOutNodes(ego)
            alter_neighs = self.graph.getInOutNodes(alter)
 
            mutuals = list(set(ego_neighs) & set(alter_neighs))
            # strength corresponds to the number of common neighbors
            self.edge_strength[e] = len(mutuals)
 
    def edge_compare(self, edge1, edge2):
        '''
        compares edges according to their strength
        -- used as a parameter function to sort edges
 
        edges are necessarily incident to a same node
        '''
        if self.edge_strength[edge1] > self.edge_strength[edge2]:
            return -1
        elif self.edge_strength[edge1] < self.edge_strength[edge2]:
            return 1
        else:
            return 0
 
    def rank_edges(self):
        for node in self.graph.getNodes():
            self.compute_edge_strength(node)
            edges = self.graph.getInOutEdges(node)
            self.ranked_edges[node] = sorted(edges, cmp=self.edge_compare)
 
    def Jaccard(self, set1, set2):
        return float(len(set1.intersection(set2)))/float(len(set1.union(set2)))
 
    def incident_nodes(self, node, m):
        '''
        computes the set of incident vertices from m strongest ties attached to a node
        returns an ordered list of nodes
        '''
        incident_edges = self.ranked_edges[node][0:m]
        incident_nodes = []
        for e in incident_edges:
            if self.graph.source(e) == node:
                incident_nodes.append(self.graph.target(e))
            else:
                incident_nodes.append(self.graph.source(e))
        return incident_nodes
 
    def compute_edge_redundancy(self, max_rank, parametric=False):
        for e in self.graph.getEdges():
            ego = self.graph.source(e)
            alter = self.graph.target(e)
 
            ego_ranked_edges = self.ranked_edges[ego]
            alter_ranked_edges = self.ranked_edges[alter]
 
            if parametric:
                s_ego = set(self.incident_nodes(ego, max_rank))
                s_alter = set(self.incident_nodes(alter, max_rank))
                r = len(s_ego.intersection(s_alter))
            else:
                r = 0.0
                for k in range(1, max_rank + 1):
                    s_ego = set(self.incident_nodes(ego, k))
                    s_alter = set(self.incident_nodes(alter, k))
                    r = max(r, self.Jaccard(s_ego, s_alter))
            self.edge_redundancy[e] = r
 
    def simmelian_backbone(self, max_rank, redundancy_min_threshold):
        '''
        computes the Simmelian backbone according to a maximum rank for edges,
        that is redundancy will be computed but only for edges with rank below max_rank
        redundancy threshold lies in [0, 1], and makes it so that only x% of edges
        are kept as part of the backbone
        '''
        parametric = True
        if redundancy_min_threshold >= 1.0:
            # parametric case
            min_redundancy = redundancy_min_threshold
            self.compute_edge_redundancy(max_rank, True)
        else:
            # non parametric, min_threshold in [0, 1]
            self.compute_edge_redundancy(max_rank, False)
            redundancy_values = sorted([self.edge_redundancy[e] for e in self.graph.getEdges()])
            min_redundancy = redundancy_values[int((1.0 - redundancy_min_threshold) * len(redundancy_values))]
 
        sg = self.graph.addCloneSubGraph()
        sg.setName('Simmelian_maxrank_' + str(max_rank) + '_redundancymin_' + str(min_redundancy))
 
        for e in self.graph.getEdges():
            # On retire les aretes dont le rang est trop eleve et/ou la redondance trop faible
            if self.edge_redundancy[e] < min_redundancy:
                sg.delEdge(e)
 
def main(graph):
    #build(graph) # should only be run once
 
    # run the code from the original graph
    # produces a distinct subgraph each time
    dissimilarity = graph.getDoubleProperty('dissimilarity_euclidean')
    max_diss = dissimilarity.getEdgeMax()
    similarity = graph.getDoubleProperty('similarity')
    for e in graph.getEdges():
    	similarity[e] = max_diss - dissimilarity[e]
    sb = Simmelian(graph, 'similarity')
    max_rank = 10
    min_redundancy = 0.25
    sb.simmelian_backbone(max_rank, min_redundancy)

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/simmelian_backbone_de_bobo_nick.txt · Last modified: 2016/05/20 20:00 by melancon