Python: создание неориентированного взвешенного графа из матрицы совпадения

Question

Я использую Python 2.7 для создания проекта, который будет использовать данные Twitter и анализировать его. Основная идея - собрать твиты и получить самые распространенные хэштеги, используемые в этой коллекции твитов, а затем мне нужно создать граф, где хэштеги будут узлами. Если бы эти хэштеги появлялись в одном и том же твите, который был бы краем на графике, а вес этого края был бы числом совпадений. Так что я пытаюсь создать словарь словарей, используя defaultdict(lambda : defaultdict(int)) и создать график, используя networkx.from_dict_of_dicts

Мой код для создания матрицы смежности является

def coocurrence (common_entities): 


com = defaultdict(lambda : defaultdict(int)) 

# Build co-occurrence matrix 
for i in range(len(common_entities)-1):    
    for j in range(i+1, len(common_entities)): 
     w1, w2 = sorted([common_entities[i], common_entities[j]])     
     if w1 != w2: 
      com[w1][w2] += 1 


return com 

Но для того, чтобы использовать networkx.from_dict_of_dicts мне это нужно, чтобы быть в этом формате: com= {0: {1:{'weight':1}}}

У вас есть идеи, как я могу это решить? Или другой способ создания такого графа?

Answer 1

Прежде всего, сначала я бы отсортировал объекты, так что вы не постоянно выполняете сортировку внутри цикла. Тогда я бы использовал itertools.combinations, чтобы получить комбинации. Простой перевод того, что вам нужно с этими изменениями заключается в следующем:

from itertools import combinations 
from collections import defaultdict 


def coocurrence (common_entities): 

    com = defaultdict(lambda : defaultdict(lambda: {'weight':0})) 

    # Build co-occurrence matrix 
    for w1, w2 in combinations(sorted(common_entities), 2): 
     if w1 != w2: 
      com[w1][w2]['weight'] += 1 

    return com 

print coocurrence('abcaqwvv') 

Это может быть более эффективным (меньше индексации и меньше объектов, созданные), чтобы построить что-то еще, а затем генерировать свой окончательный ответ во втором цикле. Второй цикл не будет работать столько циклов, сколько первый, потому что все подсчеты уже рассчитаны. Кроме того, поскольку во втором цикле не выполняется столько циклов, может быть, что отсрочка if statement во второй цикл может сэкономить больше времени. Как обычно, запустите timeit на нескольких вариациях, если вы заботитесь, но вот один из возможных примеров решения на два контура:

def coocurrence (common_entities): 

    com = defaultdict(int) 

    # Build co-occurrence matrix 
    for w1, w2 in combinations(sorted(common_entities), 2): 
     com[w1, w2] += 1 

    result = defaultdict(dict) 
    for (w1, w2), count in com.items(): 
     if w1 != w2: 
      result[w1][w2] = {'weight': count} 
    return result 

print coocurrence('abcaqwvv')