Changeset 7972:9980f7e41b18 in orange


Ignore:
Timestamp:
06/02/11 23:10:17 (3 years ago)
Author:
miha <miha.stajdohar@…>
Branch:
default
Convert:
ea8a14ab3b5d3f8dfa05c2ae089be415f5312e8d
Message:

Added another label propagation algorithm of Loung et al, 2009

File:
1 edited

Legend:

Unmodified
Added
Removed
  • orange/Orange/network/community.py

    r7951 r7972  
    44import Orange 
    55 
    6 def label_propagation(G, results2items=0, resultHistory2items=0): 
    7     """Label propagation method from Raghavan et al., 2007 
     6def add_results_to_items(G, lblhistory): 
     7    attrs = [Orange.data.variable.Discrete('clustering label propagation', 
     8                                values=list(set([l for l in lblhistory[-1]])))] 
     9     
     10    dom = Orange.data.Domain(attrs, 0) 
     11    data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]]) 
     12    if G.items() is None: 
     13        G.set_items(data)  
     14    else:  
     15        G.set_items(Orange.data.Table([G.items(), data])) 
     16         
     17def add_history_to_items(G, lblhistory): 
     18    attrs = [Orange.data.variable.Discrete('c'+ str(i), values=list(set( \ 
     19            [l for l in lblhistory[0]]))) for i,lbls in enumerate(lblhistory)] 
     20     
     21    dom = Orange.data.Domain(attrs, 0) 
     22    # transpose history 
     23    data = map(list, zip(*lblhistory)) 
     24    data = Orange.data.Table(dom, data) 
     25    if G.items() is None: 
     26        G.set_items(data)   
     27    else:  
     28        G.set_items(Orange.data.Table([G.items(), data])) 
     29             
     30def label_propagation_hop_attenuation(G, results2items=0, resultHistory2items=0, iterations=1000, delta=0.1, node_degree_preference=0): 
     31    """Label propagation for community detection, Leung et al., 2009 
    832     
    933    :param results2items: append a new feature result to items  
     
    1539    """ 
    1640     
    17     vertices = range(G.number_of_nodes()) 
    18     labels = range(G.number_of_nodes()) 
     41    if G.is_directed(): 
     42        raise Orange.network.nx.NetworkXError("""Not allowed for directed graph 
     43              G Use UG=G.to_undirected() to create an undirected graph.""") 
     44     
     45    vertices = G.nodes() 
     46    degrees = dict(zip(vertices, [G.degree(v) for v in vertices])) 
     47    labels = dict(zip(vertices, range(G.number_of_nodes()))) 
     48    scores = dict(zip(vertices, [1] * G.number_of_nodes())) 
    1949    lblhistory = [] 
    20     #consecutiveStop = 0 
    21     for i in range(1000): 
     50    m = node_degree_preference 
     51     
     52    for i in range(iterations): 
     53        random.shuffle(vertices) 
     54        stop = 1 
     55        for v in vertices: 
     56            neighbors = G.neighbors(v) 
     57            if len(neighbors) == 0: 
     58                continue 
     59             
     60            lbls = sorted(((G.edge[v][u].get('weight', 1), labels[u], u) for u in neighbors), key=lambda x: x[1]) 
     61            lbls = [(sum(scores[u] * degrees[u]**m * weight for weight, u_label, u in group), label) for label, group in itertools.groupby(lbls, lambda x: x[1])] 
     62            max_score = max(lbls)[0] 
     63            max_lbls = [label for score, label in lbls if score >= max_score] 
     64             
     65            # only change label if it is not already one of the  
     66            # preferred (maximal) labels 
     67            if labels[v] not in max_lbls: 
     68                labels[v] = random.choice(max_lbls) 
     69                scores[v] = max(0, max(scores[u] for u in neighbors if labels[u] == labels[v]) - delta) 
     70                stop = 0 
     71             
     72        lblhistory.append([str(labels[key]) for key in sorted(labels.keys())]) 
     73        # if stopping condition is satisfied (none of the labels switched color) 
     74        if stop: 
     75            break 
     76             
     77    if results2items and not resultHistory2items: 
     78        add_results_to_items(G, lblhistory) 
     79         
     80    if resultHistory2items: 
     81        add_history_to_items(G, lblhistory) 
     82     
     83    print "iterations:", i 
     84    return labels 
     85 
     86def label_propagation(G, results2items=0, resultHistory2items=0, iterations=1000): 
     87    """Label propagation for community detection, Raghavan et al., 2007 
     88     
     89    :param results2items: append a new feature result to items  
     90        (Orange.data.Table) 
     91    :type results2items: bool 
     92    :param resultHistory2items: append new features result to items  
     93        (Orange.data.Table) after each iteration of the algorithm 
     94    :type resultHistory2items: bool 
     95    """ 
     96     
     97    def next_label(neighbors): 
     98        """Updating rule as described by Raghavan et al., 2007 
     99         
     100        Return a list of possible node labels with equal probability. 
     101        """ 
     102        lbls = sorted(labels[u] for u in neighbors) 
     103        lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)] 
     104        m = max(lbls)[0] 
     105        return [l for c, l in lbls if c >= m] 
     106     
     107    vertices = G.nodes() 
     108    labels = dict(zip(vertices, range(G.number_of_nodes())))  
     109    lblhistory = [] 
     110    for i in range(iterations): 
    22111        random.shuffle(vertices) 
    23112        stop = 1 
     
    27116                continue 
    28117             
    29             lbls = [labels[u] for u in nbh] 
    30             lbls = [(len(list(c)), l) for l, c in itertools.groupby(lbls)] 
    31             m = max(lbls)[0] 
    32             mlbls = [l for c, l in lbls if c >= m] 
    33             lbl = random.choice(mlbls) 
     118            max_lbls = next_label(nbh) 
    34119             
    35             if labels[v] not in mlbls: stop = 0 
    36             labels[v] = lbl 
     120            if labels[v] not in max_lbls: 
     121                stop = 0 
    37122             
    38         lblhistory.append([str(l) for l in labels]) 
     123            labels[v] = random.choice(max_lbls) 
     124             
     125        lblhistory.append([str(labels[key]) for key in sorted(labels.keys())]) 
    39126        # if stopping condition might be satisfied, check it 
     127        # stop when no label would switch anymore 
    40128        if stop: 
    41129            for v in vertices: 
    42130                nbh = G.neighbors(v) 
    43                 if len(nbh) == 0: continue 
    44                 lbls = [labels[u] for u in nbh] 
    45                 lbls = [(len(list(c)), l) for l, c \ 
    46                         in itertools.groupby(lbls)] 
    47                 m = max(lbls)[0] 
    48                 mlbls = [l for c, l in lbls if c >= m] 
    49                 if labels[v] not in mlbls:  
     131                if len(nbh) == 0:  
     132                    continue 
     133                max_lbls = next_label(nbh) 
     134                if labels[v] not in max_lbls:  
    50135                    stop = 0 
    51136                    break 
     137             
    52138            if stop: break 
    53139                 
    54140    if results2items and not resultHistory2items: 
    55         attrs = [Orange.data.variable.Discrete( 
    56                                     'clustering label propagation', 
    57                                     values=list(set([l for l \ 
    58                                                     in lblhistory[-1]])))] 
    59         dom = Orange.data.Domain(attrs, 0) 
    60         data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]]) 
    61         if G.items() is None: 
    62             G.set_items(data)   
    63         else:  
    64             G.set_items(Orange.data.Table([G.items(), data])) 
     141        add_results_to_items(G, lblhistory) 
     142         
    65143    if resultHistory2items: 
    66         attrs = [Orange.data.variable.Discrete('c'+ str(i), 
    67             values=list(set([l for l in lblhistory[0]]))) for i,labels \ 
    68             in enumerate(lblhistory)] 
    69         dom = Orange.data.Domain(attrs, 0) 
    70         # transpose history 
    71         data = map(list, zip(*lblhistory)) 
    72         data = Orange.data.Table(dom, data) 
    73         if G.items() is None: 
    74             G.set_items(data)   
    75         else:  
    76             G.set_items(Orange.data.Table([G.items(), data])) 
    77  
     144        add_history_to_items(G, lblhistory) 
     145         
     146    print "iterations:", i 
    78147    return labels 
Note: See TracChangeset for help on using the changeset viewer.