동아리 검출 K - Shell 알고리즘

5402 단어 communitydetection
본 고 는 노드 중요성 도량형 알고리즘 원리 와 Python 실현 을 간단하게 소개 한다.
기본 사상
K - 셸 방법 은 네트워크 에서 도수 가 k 보다 작 거나 같은 노드 를 재 귀적 으로 박리 하고 구체 적 인 구분 과정 은 다음 과 같다. 네트워크 에 도수 가 0 인 고립 된 노드 가 존재 하지 않 는 다 고 가정 한다.도 지표의 측면 에서 분석 하면 도수 가 1 인 노드 는 네트워크 에서 가장 중요 하지 않 은 노드 이기 때문에 먼저 도수 가 1 인 노드 와 그 연결 을 네트워크 에서 삭제한다.삭제 작업 이 진 행 된 네트워크 에 새로운 도수 가 1 인 노드 가 나타 나 고 이 어 새로 나타 난 도수 가 1 인 노드 와 그 연결 을 삭제 합 니 다.네트워크 에 도수 가 1 인 노드 가 새로 나타 나 지 않 을 때 까지 이 동작 을 반복 합 니 다.이때 삭 제 된 모든 노드 는 1 층, 즉 1 - 셸 을 구성 하고 노드 의 Ks 값 은 1 과 같다.남 은 네트워크 에서 각 노드 의 도 수 는 적어도 2 이다.상기 삭제 작업 을 계속 반복 하면 Ks 값 이 2 인 2 층, 즉 2 - 셸 을 얻 을 수 있 습 니 다.이 유추 에 따 르 면 네트워크 의 모든 노드 에 Ks 값 이 부 여 될 때 까지.
파 이 썬 구현
# -*- coding: UTF-8 -*-

"""
Created on 17-12-17

@summary: KShell         

@author: dreamhome
"""
from get_graph import read_graph_from_file


def kshell(graph):
    """
      Kshell          
    :param graph:  
    :return: importance_dict{ks:[nodes]}
    """
    importance_dict = {}
    ks = 1
    while graph.nodes():
        #     ks   
        temp = []
        node_degrees_dict = graph.degree()
        #                   ks          。            。
        kks = min(node_degrees_dict.values())
        while True:
            for k, v in node_degrees_dict.items():
                if v == kks:
                    temp.append(k)
                    graph.remove_node(k)
            node_degrees_dict = graph.degree()
            if kks not in node_degrees_dict.values():
                break
        importance_dict[ks] = temp
        ks += 1
    return importance_dict


if __name__ == "__main__":
    # graph = nx.Graph()
    # graph.add_edges_from(
    #     [(1, 4), (2, 4), (3, 4), (4, 5), (5, 6), (5, 7), (3, 5), (6, 7)])
    # print kshell(graph)
    path = "/home/dreamhome/network-datasets/karate/karate.paj"
    graph = read_graph_from_file(path)
    print kshell(graph)


알고리즘 에 존재 하 는 문제점
  • 마지막 고립 점 을 삭제 하면 어떻게 해결 합 니까?
  • 가장 자 리 를 삭제 한 후에 노드 의 도가 Ks 보다 작 으 면 어떻게 처리 합 니까?
  • 좋은 웹페이지 즐겨찾기