Оптимизация анализа графов / распознавания образов - PullRequest
Новая
       10

Оптимизация анализа графов / распознавания образов

0 голосов
/ 09 мая 2019

Я пишу скрипт на Python для извлечения частых одновременных соединений между помеченными узлами в большом наборе данных графиков (> 100 000 графов за раз, каждый с 10-20 узлами). Есть ли лучший способ сделать это в приличное количество времени?

На данный момент мое решение состоит в создании матрицы смежности для каждого графа и извлечении соединений оттуда. 

''''''''''''''''''
create idconn X graph matrix
mat = np.zeros([graph, node, node]) is the adjacency matrix of the dataset
idconn = 2*node is the maximum number of possible connections between 
nodes (this is mandatory)
sel_conn = 10 for my example
''''''''''''''''''
def arr_bidim(mat):
    arr_bd = np.zeros([idconn, graph])
    for i in range(0, graph):
        for x in range(0, node):
            for j in range(0, node):
                if arr_bd[(j,i)] == 0 and x == 0:
                    arr_bd[(j,i)] = mat[(i,x,j)] 
                if arr_bd[(node+x,i)] == 0 and x == j:
                    if x == 0:
                        arr_bd[(node+x,i)] = 0
                    else:
                        arr_bd[(node+x,i)] = mat[(i,x,j)] 
    return arr_bd

''''''''''''''''''
create the array with the most frequent connections
''''''''''''''''''

def frq(arr_bd):
    arr_f = np.zeros([idconn, 4])
    for x in range(0, idconn): #finds the most frequent connection
        for i in range(0, graph):
            arr_f[(x,1)] += arr_bd[(x,i)]
        arr_f[(x,0)] = x
        if arr_f[(x, 1)] == graph:
            arr_f[(x, 1)] = 0
    arr_f = np.flipud(arr_f[arr_f[:,1].argsort(kind='quicksort')]) 
    arr_f = np.delete(arr_f, slice(sel_conn, idconn), axis = 0)
    return arr_f

''''''''''''''''
"cluster" the co-occurring connections
''''''''''''''''

def find_cluster():
    arr_bd = arr_bidim(mat)
    arr_f = frq(arr_bd)
    temp = np.zeros([idconn])
    for t in range(0, sel_conn):
        i = int(arr_f[(t,0)]) 
        for x in range(0, idconn): 
            temp[x] = 0
            if x != i:
                for y in range(0, graph):
                    if (arr_bd[(i,y)] == 1) & (arr_bd[(x,y)] == 1):
                        temp[x] += 1
                    if (arr_f[(t,3)] < temp[x]):
                        arr_f[(t,3)] = temp[x]
                        arr_f[(t,2)] = x
    return arr_f

 arr_f = find_cluster()

Это выполняется примерно за 1 мин 20 с. Я хотел бы понять, возможно ли каким-либо образом оптимизировать это или есть другие алгоритмы, которые могут давать аналогичные результаты в любой ситуации (то есть большие наборы данных или более двух соединений, обнаруженных как «шаблон»)

...