Ignore:
Timestamp:
02/04/12 19:00:53 (2 years ago)
Author:
Miha Stajdohar <miha.stajdohar@…>
Branch:
default
rebase_source:
45f2bb328e9f62a4232511d95325038d8c9fb22a
Message:

Fixed a bug when appending clustering results multiple times.

File:
1 edited

Legend:

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

    r8042 r9629  
    1 """  
     1""" 
    22.. index:: community detection in graphs 
    33 
     
    1414import itertools 
    1515 
    16 import Orange 
     16import Orange.core 
     17import Orange.data 
     18import Orange.network 
     19 
    1720 
    1821def add_results_to_items(G, lblhistory): 
     22    items = G.items() 
     23    if items is not None and 'clustering label propagation' in items.domain: 
     24        exclude = [attr for attr in items.domain if attr.name == \ 
     25                   'clustering label propagation'] 
     26        items = Orange.core.Preprocessor_ignore(items, attributes=exclude) 
     27 
    1928    attrs = [Orange.data.variable.Discrete('clustering label propagation', 
    20                                 values=list(set([l for l in lblhistory[-1]])))] 
    21      
     29                            values=list(set([l for l in lblhistory[-1]])))] 
     30 
    2231    dom = Orange.data.Domain(attrs, 0) 
    2332    data = Orange.data.Table(dom, [[l] for l in lblhistory[-1]]) 
    24     if G.items() is None: 
    25         G.set_items(data)  
    26     else:  
    27         G.set_items(Orange.data.Table([G.items(), data])) 
    28          
     33 
     34    if items is None: 
     35        G.set_items(data) 
     36    else: 
     37        G.set_items(Orange.data.Table([items, data])) 
     38 
     39 
    2940def add_history_to_items(G, lblhistory): 
    30     attrs = [Orange.data.variable.Discrete('c'+ str(i), values=list(set( \ 
    31             [l for l in lblhistory[0]]))) for i,lbls in enumerate(lblhistory)] 
    32      
     41    items = G.items() 
     42    if items is not None: 
     43        exclude = [attr for attr in items.domain if attr.name in \ 
     44                   ['c' + str(i) for i in range(1000)]] 
     45        items = Orange.core.Preprocessor_ignore(items, attributes=exclude) 
     46 
     47    attrs = [Orange.data.variable.Discrete('c' + str(i), values=list(set(\ 
     48            [l for l in lblhistory[0]]))) for i, _ in enumerate(lblhistory)] 
     49 
    3350    dom = Orange.data.Domain(attrs, 0) 
    3451    # transpose history 
    3552    data = map(list, zip(*lblhistory)) 
    3653    data = Orange.data.Table(dom, data) 
    37     if G.items() is None: 
    38         G.set_items(data)   
    39     else:  
    40         G.set_items(Orange.data.Table([G.items(), data])) 
    41              
    42 def label_propagation_hop_attenuation(G, results2items=0, resultHistory2items=0, iterations=1000, delta=0.1, node_degree_preference=0): 
     54    if items is None: 
     55        G.set_items(data) 
     56    else: 
     57        G.set_items(Orange.data.Table([items, data])) 
     58 
     59 
     60def label_propagation_hop_attenuation(G, results2items=0, \ 
     61                                      resultHistory2items=0, iterations=1000, \ 
     62                                      delta=0.1, node_degree_preference=0): 
    4363    """Label propagation for community detection, Leung et al., 2009 
    44      
     64 
    4565    :param G: A Orange graph. 
    4666    :type G: Orange.network.Graph 
    47      
    48     :param results2items: Append a new feature result to items  
     67 
     68    :param results2items: Append a new feature result to items 
    4969        (Orange.data.Table). 
    5070    :type results2items: bool 
    51      
    52     :param resultHistory2items: Append new features result to items  
     71 
     72    :param resultHistory2items: Append new features result to items 
    5373        (Orange.data.Table) after each iteration of the algorithm. 
    5474    :type resultHistory2items: bool 
    55      
    56     :param iterations: The maximum number of iterations if there is no convergence.  
     75 
     76    :param iterations: The max. number of iterations if no convergence. 
    5777    :type iterations: int 
    58      
    59     :param delta: The hop attenuation factor.  
     78 
     79    :param delta: The hop attenuation factor. 
    6080    :type delta: float 
    61      
    62     :param node_degree_preference: The power on node degree factor.  
     81 
     82    :param node_degree_preference: The power on node degree factor. 
    6383    :type node_degree_preference: float 
    64      
     84 
    6585    """ 
    66      
     86 
    6787    if G.is_directed(): 
    6888        raise Orange.network.nx.NetworkXError("""Not allowed for directed graph 
    6989              G Use UG=G.to_undirected() to create an undirected graph.""") 
    70      
     90 
    7191    vertices = G.nodes() 
    7292    degrees = dict(zip(vertices, [G.degree(v) for v in vertices])) 
     
    7595    lblhistory = [] 
    7696    m = node_degree_preference 
    77      
     97 
    7898    for i in range(iterations): 
    7999        random.shuffle(vertices) 
     
    83103            if len(neighbors) == 0: 
    84104                continue 
    85              
    86             lbls = sorted(((G.edge[v][u].get('weight', 1), labels[u], u) for u in neighbors), key=lambda x: x[1]) 
    87             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])] 
     105 
     106            lbls = sorted(((G.edge[v][u].get('weight', 1), labels[u], u) \ 
     107                           for u in neighbors), key=lambda x: x[1]) 
     108            lbls = [(sum(scores[u] * degrees[u] ** m * weight for weight, \ 
     109                         _u_label, u in group), label) for label, group in \ 
     110                    itertools.groupby(lbls, lambda x: x[1])] 
    88111            max_score = max(lbls)[0] 
    89112            max_lbls = [label for score, label in lbls if score >= max_score] 
    90              
    91             # only change label if it is not already one of the  
     113 
     114            # only change label if it is not already one of the 
    92115            # preferred (maximal) labels 
    93116            if labels[v] not in max_lbls: 
    94117                labels[v] = random.choice(max_lbls) 
    95                 scores[v] = max(0, max(scores[u] for u in neighbors if labels[u] == labels[v]) - delta) 
     118                scores[v] = max(0, max(scores[u] for u in neighbors \ 
     119                                       if labels[u] == labels[v]) - delta) 
    96120                stop = 0 
    97              
     121 
    98122        lblhistory.append([str(labels[key]) for key in sorted(labels.keys())]) 
    99         # if stopping condition is satisfied (none of the labels switched color) 
     123        # if stopping condition is satisfied (no label switched color) 
    100124        if stop: 
    101125            break 
    102              
     126 
    103127    if results2items and not resultHistory2items: 
    104128        add_results_to_items(G, lblhistory) 
    105          
     129 
    106130    if resultHistory2items: 
    107131        add_history_to_items(G, lblhistory) 
    108      
    109     print "iterations:", i 
     132 
     133    #print "iterations:", i 
    110134    return labels 
    111135 
    112 def label_propagation(G, results2items=0, resultHistory2items=0, iterations=1000): 
     136 
     137def label_propagation(G, results2items=0, \ 
     138                      resultHistory2items=0, iterations=1000): 
    113139    """Label propagation for community detection, Raghavan et al., 2007 
    114      
     140 
    115141    :param G: A Orange graph. 
    116142    :type G: Orange.network.Graph 
    117      
    118     :param results2items: Append a new feature result to items  
     143 
     144    :param results2items: Append a new feature result to items 
    119145        (Orange.data.Table). 
    120146    :type results2items: bool 
    121      
    122     :param resultHistory2items: Append new features result to items  
     147 
     148    :param resultHistory2items: Append new features result to items 
    123149        (Orange.data.Table) after each iteration of the algorithm. 
    124150    :type resultHistory2items: bool 
    125      
     151 
    126152    :param iterations: The maximum number of iterations if there is no convergence.  
    127153    :type iterations: int 
    128      
     154 
    129155    """ 
    130      
     156 
    131157    def next_label(neighbors): 
    132158        """Updating rule as described by Raghavan et al., 2007 
    133          
     159 
    134160        Return a list of possible node labels with equal probability. 
    135161        """ 
     
    138164        m = max(lbls)[0] 
    139165        return [l for c, l in lbls if c >= m] 
    140      
     166 
    141167    vertices = G.nodes() 
    142     labels = dict(zip(vertices, range(G.number_of_nodes())))  
     168    labels = dict(zip(vertices, range(G.number_of_nodes()))) 
    143169    lblhistory = [] 
    144170    for i in range(iterations): 
     
    149175            if len(nbh) == 0: 
    150176                continue 
    151              
     177 
    152178            max_lbls = next_label(nbh) 
    153              
     179 
    154180            if labels[v] not in max_lbls: 
    155181                stop = 0 
    156              
     182 
    157183            labels[v] = random.choice(max_lbls) 
    158              
     184 
    159185        lblhistory.append([str(labels[key]) for key in sorted(labels.keys())]) 
    160186        # if stopping condition might be satisfied, check it 
     
    163189            for v in vertices: 
    164190                nbh = G.neighbors(v) 
    165                 if len(nbh) == 0:  
     191                if len(nbh) == 0: 
    166192                    continue 
    167193                max_lbls = next_label(nbh) 
    168                 if labels[v] not in max_lbls:  
     194                if labels[v] not in max_lbls: 
    169195                    stop = 0 
    170196                    break 
    171              
    172             if stop: break 
    173                  
     197 
     198            if stop: 
     199                break 
     200 
    174201    if results2items and not resultHistory2items: 
    175202        add_results_to_items(G, lblhistory) 
    176          
     203 
    177204    if resultHistory2items: 
    178205        add_history_to_items(G, lblhistory) 
    179          
    180     print "iterations:", i 
     206 
     207    #print "iterations:", i 
    181208    return labels 
Note: See TracChangeset for help on using the changeset viewer.