サークル検出のLeaderRankアルゴリズム

本論文では,主にコミュニティ検出におけるノードソートLeaderRankアルゴリズムを紹介する.
基本思想.
LeaderRank L e a d e r R a n kアルゴリズムは,ネットワークに1つのノードg(Groundnode)g(G r o u n d n o d e)を追加することにより,ネットワーク内のすべてのノードに接続し,強い接続N+1 N+1ノードの新しいネットワークを得る.アルゴリズムは、まず、ノードg以外のN個のノードに1単位のLR値を割り当て、この1単位のLR値を直接接続された隣接ノードに割り当てる.
si(t+1)=∑j=0Naijkjsj(t) s i ( t + 1 ) = ∑ j = 0 N a i j k j s j ( t )
ただし、ノードiとjが直接接続すると
aij=1 a i j=1であり、そうでなければ0である.
kj k jはノードjの度数を表す.
aijkj a i j k jはノードを表す
iランダムウォーク
j jの確率.初期状態で除く
g g g以外のすべてのノードの
Si(0)=1 s i(0)=1であり、
sg(0)=0 s g ( 0 ) = 0 .最後にノードを
g gの
LR L R値は他に均等に分けられる
N N個のノード:
Si=si(tc)+sg(tc)⋅N−1 S i = s i ( t c ) + s g ( t c ) ⋅ N − 1
ここで、
sg(tc)s g(t c)は安定状態におけるノードである
g gの
LR L R値、
tc t cは収束回数を表す.
参考論文:Leaders in Social Networks,the Delicious Case
Pythonコード実装

# -*- coding: UTF-8 -*-

"""
Created on 18-3-5

@summary: LeaderRank       

@author: dreamhomes
"""
import get_graph


def leaderrank(graph):
    """
        
    :param graph:     Graph
    :return:        
    """
    #     
    num_nodes = graph.number_of_nodes()
    #   
    nodes = graph.nodes()
    #         g           
    graph.add_node(0)
    for node in nodes:
        graph.add_edge(0, node)
    # LR    
    LR = dict.fromkeys(nodes, 1.0)
    LR[0] = 0.0
    #           
    while True:
        tempLR = {}
        for node1 in graph.nodes():
            s = 0.0
            for node2 in graph.nodes():
                if node2 in graph.neighbors(node1):
                    s += 1.0 / graph.degree([node2])[node2] * LR[node2]
            tempLR[node1] = s
        #     :LR     
        error = 0.0
        for n in tempLR.keys():
            error += abs(tempLR[n] - LR[n])
        if error == 0.0:
            break
        LR = tempLR
    #   g LR        N         
    avg = LR[0] / num_nodes
    LR.pop(0)
    for k in LR.keys():
        LR[k] += avg

    return LR


if __name__ == "__main__":
    path = "/home/dreamhome/network-datasets/karate/karate.paj"
    graph = get_graph.read_graph_from_file(path)
    print sorted(leaderrank(graph).items(), key=lambda item: item[1])