동아리 검출 K - Shell 알고리즘
기본 사상
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)
알고리즘 에 존재 하 는 문제점
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
AZ DEVOPS를 사용하여 AAD 그룹 만들기이 세션에서는 Azure DevOps를 사용하여 AAD(Azure Active Directory) 그룹을 만드는 방법을 시연합니다. 중요 사항:- 이름이 같은 AAD 그룹을 하나 이상 만들 수 있습니다. AAD 그룹...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.