KR102409160B1

KR102409160B1 - 복수개의 커뮤니티를 포함하는 네트워크에서 커뮤니티 재구성 방법 및 이를 위한 전자 장치

Info

Publication number: KR102409160B1
Application number: KR1020190146099A
Authority: KR
Inventors: 김상욱; 강윤석; 이준석
Original assignee: 한양대학교 산학협력단
Priority date: 2019-11-14
Filing date: 2019-11-14
Publication date: 2022-06-14
Anticipated expiration: 2039-11-14
Also published as: KR20210058533A

Abstract

본 발명은 제1 커뮤니티와 제2 커뮤니티를 포함하는 네트워크에서 상기 네트워크를 구성하는 노드 간의 유사도를 결정하는 단계, 상기 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정하는 단계, 상기 제1 커뮤니티의 품질 특성에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지의 양을 결정하는 단계 및 상기 결정된 추가 또는 제거되어야 하는 엣지의 양에 기반하여 상기 제1 커뮤니티에 엣지를 추가 또는 제거함으로써 상기 제1 커뮤니티를 재구성하는 단계를 포함하는 커뮤니티 재구성 방법을 제공한다.

Description

복수개의 커뮤니티를 포함하는 네트워크에서 커뮤니티 재구성 방법 및 이를 위한 전자 장치{METHOD FOR RECONFIGURATION OF A COMMUNITY IN A NETWORK INCLUDING A PLURALITY OF NETWORKS AND AN ELECTRONIC DEVICE FOR THE METHOD}

본 발명은 복수개의 커뮤니티를 포함하는 네트워크에서 커뮤니티를 재구성하는 방법 및 이를 위한 전자 장치에 관한 것이다.z

소셜 네트워크 분석은 데이터 마이닝 및 머신러닝 분야에서 가장 주목받고 있는 문제 중 하나이다. 점점 많은 사람들이 소셜 네트워크에 참여하고 있으므로, 소셜 네트워크 분석은 소셜 네트워크 서비스를 이용하는 사람들의 행동을 이용하여 실세계 사람들 행동에 대한 중요한 실마리와 다른 사람들과의 관계를 제공해준다. 또한 소셜 네트워크 분석은 경제, 역학, 정치, 심리학 등 다양한 분야에서 중요한 기술로써 사용되고 있다. 이러한 소셜 네트워크 분석 방법 중 커뮤니티 검출에 대한 중요성이 증가하고 있다.

커뮤니티 검출은 그래프 내 노드들의 구조를 찾기 위한 중요한 기술 중에 하나이다. 커뮤니티는 그래프 내 노드들의 집합을 의미하는데, 같은 커뮤니티 내의 노드들은 밀도가 높은 특징이 있고, 서로 다른 커뮤니티 간의 노드들은 밀도가 낮은 특징이 있다.

커뮤니티 검출 방법은 크게 두 가지 방법이 존재하는데, 그 중 하나는 그래프의 노드와 엣지 정보만을 이용하여 커뮤니티 검출을 수행하는 방법이고, 나머지 하나는 그래프의 노드 간 유사도를 이용하여 커뮤니티 검출을 수행하는 방법이다.

그러나 종래에는 커뮤니티 구조가 잘 드러나지 않는 그래프에서 커뮤니티 검출을 수행하기 때문에, 특정 노드가 정확히 어느 커뮤니티에 속해야 하는지 애매한 상황이 발생할 수 있고, 이는 커뮤니티 검출을 어렵게 만들며 정확도를 낮추는 문제가 있다.

따라서, 커뮤니티 구조가 잘 드러나지 않은 그래프를 커뮤니티 구조가 잘 드러나는 그래프로 만들어, 더 쉽고 정확하게 커뮤니티 검출을 수행할 수 있도록 하는 기술 개발이 필요한 실정이다.

종래에는 커뮤니티 구성의 정확도를 향상시키기 위해 주어진 그래프의 엣지에 비중을 부과하는 방안이 존재하였다. 그러나, 엣지에 비중을 부과하는 방식을 이용하는 경우 커뮤니티를 구성할 때 엣지의 비중을 고려할 수 있는 알고리즘에만 적용이 가능하다는 문제점이 존재하였다.

따라서 본 발명에서는 적용되는 알고리즘에 관계없이 커뮤니티의 구조를 강화할 수 있는 커뮤니티 재구성 방법을 제공하고자 한다.

일 실시예에 따르면, 상기 엣지를 결정하는 단계는 상기 결정된 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에 추가되어야 하는 엣지로 판단하는 단계 및 상기 결정된 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에서 제거되어야 하는 엣지로 판단하는 단계를 포함할 수 있다.

일 실시예에 따르면, 상기 엣지의 양을 결정하는 단계는 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 상기 제1 커뮤니티에 추가하는 단계, 상기 제1 엣지가 추가된 상기 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는지 여부를 판단하는 단계 및 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제2 커뮤니티에 추가하는 단계를 포함할 수 있다.

일 실시예에 따르면, 상기 제1 엣지가 추가된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티를 벗어나지 않는 경우, 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 것으로 판단할 수 있다.

일 실시예에 따르면, 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티로 엣지를 추가하는 것을 정지하는 단계를 더 포함할 수 있다.

일 실시예에 따르면, 상기 엣지의 양을 결정하는 단계는 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 상기 제1 커뮤니티에서 제거하는 단계, 상기 제3 엣지가 제거된 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는지 여부를 판단하는 단계 및 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거하는 단계를 포함할 수 있다.

일 실시예에 따르면, 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에서 엣지를 제거하는 것을 정지하는 단계를 더 포함할 수 있다.

일 실시예에 따르면, 상기 노드간의 유사도를 결정하는 단계는 상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하는 단계 및 상기 구별된 노드간의 유사도를 결정하는 단계를 포함할 수 있다.

일 실시예에 따르면, 제1 커뮤니티와 제2 커뮤니티를 포함하는 네트워크에서 커뮤니티를 재구성하기 위한 전자 장치는 상기 네트워크를 구성하는 노드 간의 유사도를 결정하는 유사도 결정부, 상기 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정하며, 상기 제1 커뮤니티의 품질 특성에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지의 양을 결정하는 엣지 결정부 및 상기 결정된 추가 또는 제거되어야 하는 엣지의 양에 기반하여 상기 제1 커뮤니티에 엣지를 추가 또는 제거함으로써 상기 제1 커뮤니티를 재구성하는 커뮤니티 재구성부를 포함할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 결정된 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에 추가되어야 하는 엣지로 판단하고, 상기 결정된 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에서 제거되어야 하는 엣지로 판단할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 상기 제1 커뮤니티에 추가하고, 상기 제1 엣지가 추가된 상기 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는지 여부를 판단하며, 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제2 커뮤니티에 추가할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 제1 엣지가 추가된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티를 벗어나지 않는 경우, 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 것으로 판단할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티로 엣지를 추가하는 것을 정지할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 상기 제1 커뮤니티에서 제거하고, 상기 제3 엣지가 제거된 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는지 여부를 판단하며, 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에서 엣지를 제거할 수 있다.

일 실시예에 따르면, 상기 유사도 결정부는 상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하고, 상기 구별된 노드간의 유사도를 결정할 수 있다.

본 발명에서 개시하고 있는 일 실시예에 따르면, 엣지를 결정하는 알고리즘의 방식에 관계없이 커뮤니티 구조를 강화할 수 있다. 뿐만 아니라, 본 발명에서 개시하고 있는 일 실시예에 따르면, 커뮤니티에 추가되는 엣지의 양 및 유사도를 결정하는 노드의 양이 제한될 수 있으므로 커뮤니티 구조 강화에 부담되는 부하가 감소할 수 있다.

도 1은 본 발명의 일 실시예에 따른 커뮤니티 재구성 방법을 설명하기 위한 도면이다.
도 2는 본 발명의 일 실시예에 따른 커뮤니티 재구성 방법에 대한 흐름도이다.
도 3은 본 발명의 일 실시예에 따른 엣지를 추가 또는 제거하는 방법에 대한 흐름도이다.
도 4는 본 발명의 일 실시예에 따른 엣지를 추가하는 양을 결정하는 방법에 대한 흐름도이다.
도 5는 본 발명의 일 실시예에 따른 엣지를 제거하는 양을 결정하는 방법에 대한 흐름도이다.
도 6은 본 발명의 일 실시예에 따른 전자 장치의 블록도이다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세한 설명에 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다. 각 도면을 설명하면서 유사한 참조부호를 유사한 구성요소에 대해 사용하였다.

제1, 제2, A, B 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의 조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.

어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다.

본 출원에서 사용한 용어는 단지 특정한 실시예를 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함하다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.

다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥 상 가지는 의미와 일치하는 의미를 가지는 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다.

도 1은 본 발명의 일 실시예에 따른 커뮤니티 재구성 방법을 설명하기 위한 도면이다. 도 1은 네트워크를 구성하는 커뮤니티 구조에 대한 그래프를 도시한 것이다.

일 실시예에 따르면, 네트워크는 제1 커뮤니티(110)와 제2 커뮤니티(120)를 포함할 수 있다. 다양한 실시예에 따르면 종래 그래프(original graph)에서 제1 커뮤니티(110)는 다섯 개의 노드(0번 노드, 1번 노드, 2번 노드, 3번 노드, 4번 노드)를 포함할 수 있으며 제2 커뮤니티(120)도 다섯 개의 노드(5번 노드, 6번 노드, 7번 노드, 8번 노드, 9번 노드)를 포함할 수 있다.

일 실시예에 따르면, 종래 그래프에서 제1 커뮤니티(110)를 구성하는 0번 노드와 3번 노드 사이와 0번 노드와 2번 노드 사이에는 엣지가 형성되지 않을 수 있다. 네트워크 내에서 제1 커뮤니티(110)의 구조가 강화되기 위해서는 제1 커뮤니티를 구성하는 노드간 엣지의 양이 증가할 필요가 있다. 따라서 커뮤니티 내 엣지를 추가하는 단계(adding intra-community edges)를 통해 제1 커뮤니티(110)를 구성하는 0번 노드와 3번 노드 사이에 제1 엣지(131)를 추가할 수 있으며, 0번 노드와 2번 노드 사이에 제2 엣지(132)를 추가할 수 있다.

일 실시예에 따르면, 종래 그래프에서 제1 커뮤니티(110)를 구성하는 노드 중 0번 노드는 제2 커뮤니티(120)를 구성하는 9번 노드와 제3 엣지(141)를 형성할 수 있으며, 제1 커뮤니티(110)를 구성하는 2번 노드는 제2 커뮤니티(120)를 구성하는 5번 노드와 제4 엣지(142)를 형성할 수 있고, 제1 커뮤니티(110)를 구성하는 3번 노드는 제2 커뮤니티(120)를 구성하는 8번 노드와 제5 엣지를 형성할 수 있다. 다양한 실시예에 따르면, 제1 커뮤니티(110)를 구성하는 노드와 제2 커뮤니티(120)를 구성하는 노드간의 엣지로 인해 커뮤니티 구조의 정확도가 감소할 수 있다. 즉, SNS(social network service) 같은 네트워크 환경에서 서로 상이한 상향을 보이는 사용자 간에 엣지가 형성될 수 있으며, 이로 인해 사용자 그룹의 그룹화에 대한 정확도가 감소할 수 있다.

따라서 네트워크 내에서 제1 커뮤니티(110)의 구조가 강화되기 위해서는 제1 커뮤니티(110)를 구성하는 노드와 제2 커뮤니티(120)를 구성하는 노드간 엣지의 양을 감소시킬 필요가 있다. 이에 따라 커뮤니티간 엣지를 제거하는 단계(deleting inter-community edges)를 통해 제1 커뮤니티(110)를 구성하는 0번 노드와 제2 커뮤니티(120)를 구성하는 9번 노드 사이의 제3 엣지(141)와 제1 커뮤니티(110)를 구성하는 3번 노드와 제2 커뮤니티(120)를 구성하는 8번 노드 사이의 제4 엣지(142)를 제거할 수 있다.

일 실시예에 따르면, 도 1에서 도시하고 있는 (B)와 (C)에서 개시하고 있는 단계를 통해 종래 그래프인 (A) 그래프는 (D) 그래프로 변경될 수 있다. 다양한 실시예에 따르면, (D) 그래프에서 도시하고 있는 제1 커뮤니티(110)는 (A) 그래프에서 도시하고 있는 제1 커뮤니티(110)보다 제1 커뮤니티(110) 내에 형성되는 엣지의 수가 많을 뿐만 아니라, 제2 커뮤니티(120)와 연결되는 엣지의 수는 적으므로 커뮤니티의 구조의 정확도가 높을 수 있다. 따라서 본 발명에서 개시하고 있는 일 실시예에 따를 경우, 네트워크를 구성하는 커뮤니티의 구조가 강화될 수 있다.

도 2는 본 발명의 일 실시예에 따른 커뮤니티 재구성 방법에 대한 흐름도이다. 일 실시예에 따르면, 도 2에서 도시하고 있는 흐름도는 도 6에서 도시하고 있는 전자 장치에 의해 수행될 수 있다.

일 실시예에 따르면, S210 단계에서 네트워크를 구성하는 노드간의 유사도를 결정할 수 있다. 다양한 실시예에 따르면, 네트워크를 구성하는 노드간의 유사도는 해당 노드의 특성에 기반하여 결정될 수 있다. 예를 들어, 쇼핑몰과 관련된 네트워크를 가정한다면 특정 상품에 대한 선호도가 높은 노드들은 유사도가 높은 노드라고 판단할 수 있다.

일 실시예에 따르면, S210 단계는 상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하는 단계 및 상기 구별된 노드간의 유사도를 결정하는 단계를 포함할 수 있다. 다양한 실시예에 따르면, 상기 제3 임계값을 초과하는 노드만을 구별하여 유사도를 결정함으로써 유사도 결정에 부담되는 부하를 감소시킬 수 있다. 예를 들어, 네트워크를 구성하는 노드가 1000개인 경우 노드 1000개의 유사도를 모두 결정하는 것보다 제1 커뮤니티에 포함될 확률이 높은 노드 100개만을 구별하여 노드 100개에 대한 유사도를 결정하는 것이 바람직할 수 있다.

일 실시예에 따르면, S220 단계에서 S210 단계를 통해 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정할 수 있다. 다양한 실시예에 따르면, S220 단계를 통해 현재의 그래프에서 커뮤니티 구조 강화를 위해 추가 또는 제거되어야 하는 엣지를 결정할 수 있다. 여기서 현재의 그래프란 도 1에서 도시한 종래 그래프를 의미하는 것으로 네트워크에서 수집된 정보에 기반한 각 노드간의 연결관계라고 볼 수 있다. S220 단계에 대한 구체적인 설명은 도 3을 통해 후술한다.

일 실시예에 따르면, S230 단계에서 상기 제1 커뮤니티의 품질 특성에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지의 양을 결정할 수 있다. 다양한 실시예에 따르면, 제1 커뮤니티에 추가 또는 제거되는 엣지의 양이 적으면 커뮤니티 구조의 정확도가 향상되는 정도가 낮을 수 있으며, 제1 커뮤니티에 추가 또는 제거되는 엣지의 양이 과도하면 커뮤니티 구조의 정확도가 오히려 감소할 수 있다. 즉, 제1 커뮤니티에 얼만큼 많은 양의 엣지를 추가 또는 제거할 것인지는 커뮤니티 구조의 정확도를 향상시키는데 있어서 중요한 요소가 될 수 있다. 따라서, 본 발명에서는 제1 커뮤니티의 품질 특성에 기반하여 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지의 양을 결정하는 방법을 개시하고자 하며, S230 단계에 대한 구체적인 설명은 도 4 및 도 5에 대한 설명을 통해 후술한다.

일 실시예에 따르면, S240 단계에서 S230 단계를 통해 결정된 추가 또는 제거되어야 하는 엣지의 양에 기반하여 상기 제1 커뮤니티에 엣지를 추가 또는 제거함으로써 상기 제1 커뮤니티를 재구성할 수 있다. 다양한 실시예에 따르면, S240 단계를 통해 제1 커뮤니티가 재구성됨으로써 커뮤니티 구조의 정확도가 향상될 수 있다.

도 3은 본 발명의 일 실시예에 따른 엣지를 추가 또는 제거하는 방법에 대한 흐름도이다. 일 실시예에 따르면, 도 3에서 도시하고 있는 흐름도는 도 6에서 도시하고 있는 전자 장치에 의해 수행될 수 있다.

일 실시예에 따르면, S310 단계에서 도 2의 S210 단계를 통해 결정된 유사도가 기설정된 제1 임계값을 초과하는지 여부를 판단할 수 있다. 다양한 실시예에 따르면, 유사도가 기설정된 제1 임계값을 초과하는 경우, S320 단계에서 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서 제1 커뮤니티에 추가되어야 하는 엣지로 결정할 수 있다. 예를 들어, 결정된 유사도 중에서 노드 간의 유사도가 80%를 초과하는 경우의 엣지에 대해 제1 커뮤니티에 추가되어야 하는 엣지로 결정할 수 있다.

일 실시예에 따르면, S320 단계는 도 1에서 설명한 (B) 그래프에 대응될 수 있다. 다양한 실시예에 따르면, 도 1 (B) 그래프에서 0번 노드와 2번 노드 사이의 엣지(132)와 0번 노드와 3번 노드 사이의 엣지(131)가 도 3의 S320 단계를 통해 결정되는 추가되어야 할 엣지가 될 수 있다. 왜냐하면 앞서 언급한 바와 같이 같은 커뮤니티에 속하는 노드 사이의 엣지는 유사도가 높을 확률이 높기 때문이다.

일 실시예에 따르면, 유사도가 기설정된 제1 임계값 이하인 경우, S330 단계에서 유사도가 기설정된 제2 임계값 미만인지 여부를 판단할 수 있다. 다양한 실시예에 따르면, 유사도가 기설정된 제2 임계값 미만인 경우, S340 단계에서 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서 제2 커뮤니티에서 제거되어야 하는 엣지로 결정할 수 있다. 예를 들어, 결정된 유사도 중에서 유사도가 20% 미만인 경우의 엣지에 대해 제1 커뮤니티에서 제거되어야 하는 엣지로 결정할 수 있다.

일 실시예에 따르면, S340 단계는 도 1에서 설명한 (C) 그래프에 대응될 수 있다. 다양한 실시예에 따르면, 도 1 (C) 그래프에서 0번 노드와 9번 노드 사이의 엣지(141)와 2번 노드와 5번 노드 사이의 엣지와 3번 노드와 8번 노드 사이의 엣지(142)가 도 4의 S340 단계를 통해 결정되는 제거되어야 할 엣지가 될 수 있다. 왜냐하면 앞서 언급한 바와 같이 서로 다른 커뮤니티에 속하는 노드 사이의 엣지는 유사도가 낮은 확률이 높기 때문이다.

일 실시예에 따르면, 유사도가 기설정된 제2 임계값 이상인 경우, S350 단계에서 유사도가 기설정된 제2 임계값 이상인 노드간을 연결하는 엣지에 대해 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지에서 제외시킬 수 있다. 다양한 실시예에 따르면, 도 1 그래프에서 1번 노드와 3번 노드 사이간 유사도가 제1 임계값 이하이면서 제2 임계값 이상일 수 있으며, 이에 따라 도 1 그래프에서는 1번 노드와 3번 노드 사이에는 엣지가 형성되지 않을 수 있다.

도 4는 본 발명의 일 실시예에 따른 엣지를 추가하는 양을 결정하는 방법에 대한 흐름도이다. 일 실시예에 따르면, 도 4에서 도시하고 있는 흐름도는 도 6에서 도시하고 있는 전자 장치에 의해 수행될 수 있다.

일 실시예에 따르면, S410 단계에서 도 2의 S220 단계를 통해 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 제1 커뮤니티에 추가할 수 있다. 다양한 실시예에 따르면, 도 1 그래프에서 0번 노드와 2번 노드 사이의 엣지(132)가 상기 제1 엣지에 대응될 수 있다.

일 실시예에 따르면, S420 단계에서 제1 엣지가 추가된 제1 커뮤니티 품질 특성이 기설정된 조건을 만족하는지 여부를 판단할 수 있다. 다양한 실시예에 따르면, 제1 엣지가 추가된 제1 커뮤니티를 구성하는 모든 엣지가 제1 커뮤니티를 벗어나지 않는 경우, 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족한다고 판단할 수 있다. 예를 들어, 도 1 그래프에서 0번 노드와 2번 노드 사이의 엣지(132)는 제1 커뮤니티 내에서 형성되는 엣지이므로 제1 엣지가 추가된 제1 커뮤니티의 품질 특성은 기설정된 조건을 만족한다고 볼 수 있다.

일 실시예에 따르면, 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는 경우, S430 단계에서 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제1 커뮤니티에 추가할 수 있다. 다양한 실시예에 따르면, 도 1 그래프에서 0번 노드와 3번 노드 사이의 엣지(131)가 상기 제2 엣지에 대응할 수 있다.

일 실시예에 따르면, 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하지 않는 경우, S440 단계에서 제1 커뮤니티로 엣지를 추가하는 것을 정지할 수 있다. 예를 들어 제1 엣지가 도 1의 4번 노드와 9번 노드 사이의 엣지인 경우, 제1 엣지는 제1 커뮤니티를 구성하는 노드와 제2 커뮤니티를 구성하는 노드 사이에 형성되는 엣지가 제1 커뮤니티에 추가되면 커뮤니티 구조의 정확도가 감소할 수 있다. 따라서 이 같은 동작으로 인해 커뮤니티 구조의 정확도가 감소하는 것을 방지하기 위해 S440 단계를 통해 커뮤니티 엣지의 추가를 정지시킬 수 있다.

한편, 도 4에서는 제2 엣지를 제1 커뮤니티 추가하는 S430 단계를 마지막 단계로 개시하고 있으나, 경우에 따라 제1 커뮤니티에 추가되는 엣지의 양은 증가 또는 감소할 수 있다. 예를 들어, 도 2의 S220 단계를 통해 제1 커뮤니티에 추가되어야 할 엣지로 5개의 엣지가 결정된 경우, 5개의 엣지 모두에 대해서 추가될 경우 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는지 여부를 판단할 수 있으며, 이에 따라 각 엣지를 제1 커뮤니티에 추가할지 여부를 결정할 수 있다. 따라서 본 발명의 권리범위가 도 4에서 도시하고 있는 흐름도에 국한되어서는 안 될 것이다.

도 5는 본 발명의 일 실시예에 따른 엣지를 제거하는 양을 결정하는 방법에 대한 흐름도이다. 일 실시예에 따르면, 도 5에서 도시하고 있는 흐름도는 도 6에서 도시하고 있는 전자 장치에 의해 수행될 수 있다.

일 실시예에 따르면, S510 단계에서 도 2의 S220 단계를 통해 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 제1 커뮤니티에서 제거할 수 있다. 다양한 실시예에 따르면, 도 1 그래프에서 0번 노드와 9번 노드 사이의 엣지(141)가 상기 제3 엣지에 대응될 수 있다.

일 실시예에 따르면, S520 단계에서 제3 엣지가 제거된 제1 커뮤니티 품질 특성이 기설정된 조건을 만족하는지 여부를 판단할 수 있다. 다양한 실시예에 따르면, 제3 엣지가 제거된 제1 커뮤니티를 구성하는 모든 엣지가 제1 커뮤니티를 벗어나지 않는 경우, 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족한다고 판단할 수 있다. 예를 들어, 도 1 그래프에서 2번 노드와 5번 노드 사이의 엣지는 제1 커뮤니티와 제1 커뮤니티 사이에 형성되는 엣지이므로 제3 엣지만이 제거된 제1 커뮤니티의 품질 특성은 기설정된 조건을 만족한다고 볼 수 없다.

일 실시예에 따르면, 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는 경우, S530 단계에서 제1 커뮤니티에서 엣지를 제거하는 것을 정지할 수 있다. 다양한 실시예에 따르면, 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하지 않는 경우, S540 단계에서 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거할 수 있다. 예를 들어, 도 1 그래프에서 3번 노드와 8번 노드 사이의 엣지(142)가 상기 제4 엣지에 대응할 수 있다.

한편, 도 5에서는 제4 엣지를 제1 커뮤니티에서 제거하는 S540 단계를 마지막 단계로 개시하고 있으나, 경우에 따라 제1 커뮤니티에서 제거되는 엣지의 양은 증가 또는 감소할 수 있다. 예를 들어, 도 2의 S220 단계를 통해 제1 커뮤니티에서 제거되어야 할 엣지로 5개의 엣지가 결정된 경우, 5개의 엣지 모두에 대해서 제거될 경우 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는지 여부를 판단할 수 있으며, 이에 따라 각 엣지를 제1 커뮤니티에서 제거할지 여부를 결정할 수 있다. 따라서 본 발명의 권리범위가 도 5에서 도시하고 있는 흐름도에 국한되어서는 안 될 것이다.

도 6은 본 발명의 일 실시예에 따른 전자 장치의 블록도이다.

일 실시예에 따르면, 제1 커뮤니티와 제2 커뮤니티를 포함하는 네트워크에서 커뮤니티를 재구성하기 위한 전자 장치(600)는 상기 네트워크를 구성하는 노드 간의 유사도를 결정하는 유사도 결정부(610), 상기 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정하며, 상기 제1 커뮤니티의 품질 특성에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지의 양을 결정하는 엣지 결정부(620) 및 상기 결정된 추가 또는 제거되어야 하는 엣지의 양에 기반하여 상기 제1 커뮤니티에 엣지를 추가 또는 제거함으로써 상기 제1 커뮤니티를 재구성하는 커뮤니티 재구성부(630) 를 포함할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부(620)는 상기 결정된 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에 추가되어야 하는 엣지로 판단하고, 상기 결정된 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에서 제거되어야 하는 엣지로 판단할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부는(620) 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 상기 제1 커뮤니티에 추가하고, 상기 제1 엣지가 추가된 상기 제1 커뮤니티의 품질 특성이 기설정된 조건을 만족하는지 여부를 판단하며, 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제2 커뮤니티에 추가할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부(620)는 상기 제1 엣지가 추가된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티를 벗어나지 않는 경우, 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 것으로 판단할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부(620)는 상기 제1 엣지가 추가된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티로 엣지를 추가하는 것을 정지할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부(620)는 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 상기 제1 커뮤니티에서 제거하고, 상기 제3 엣지가 제거된 상기 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는지 여부를 판단하며, 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하지 않는 경우, 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거할 수 있다.

일 실시예에 따르면, 상기 엣지 결정부(620)는 상기 제3 엣지가 제거된 제1 커뮤니티의 품질 특성이 상기 기설정된 조건을 만족하는 경우, 상기 제1 커뮤니티에서 엣지를 제거하는 것을 정지할 수 있다.

일 실시예에 따르면, 상기 유사도 결정부(610)는 상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하고, 상기 구별된 노드간의 유사도를 결정할 수 있다.

이제까지 본 발명에 대하여 그 바람직한 실시예들을 중심으로 살펴보았다. 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자는 본 발명이 본 발명의 본질적인 특성에서 벗어나지 않는 범위에서 변형된 형태로 구현될 수 있음을 이해할 수 있을 것이다. 그러므로 개시된 실시예들은 한정적인 관점이 아니라 설명적인 관점에서 고려되어야 한다. 본 발명의 범위는 전술한 설명이 아니라 특허청구범위에 나타나 있으며, 그와 동등한 범위 내에 있는 모든 차이점은 본 발명에 포함된 것으로 해석되어야 할 것이다.

Claims

제1 커뮤니티와 제2 커뮤니티를 포함하는 네트워크에서 커뮤니티의 재구성 방법에 있어서,
상기 네트워크를 구성하는 노드 간의 유사도를 결정하는 단계;
상기 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정하는 단계;
상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 상기 제1 커뮤니티에 추가하는 단계;
상기 제1 엣지가 추가된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티에 포함되는 경우, 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제1 커뮤니티에 추가하는 단계;
상기 제2 엣지가 추가된 상기 제1 커뮤니티를 구성하는 엣지 중 상기 제1 커뮤니티를 벗어나는 엣지가 존재하는 경우, 상기 제1 커뮤니티로 엣지를 추가하는 것을 정지하는 단계; 및
상기 제1 엣지 및 상기 제2 엣지를 상기 제1 커뮤니티에 추가함으로써 상기 제1 커뮤니티를 재구성하는 단계를 포함하는,
커뮤니티 재구성 방법.
제1항에 있어서,
상기 엣지를 결정하는 단계는,
상기 결정된 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에 추가되어야 하는 엣지로 판단하는 단계; 및
상기 결정된 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에서 제거되어야 하는 엣지로 판단하는 단계를 포함하는,
커뮤니티 재구성 방법.
삭제
삭제
삭제
제1항에 있어서,
상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 상기 제1 커뮤니티에서 제거하는 단계;
상기 제3 엣지가 제거된 상기 제1 커뮤니티를 구성하는 모든 엣지 중 상기 제1 커뮤니티를 벗어나는 엣지가 존재하는 경우, 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거하는 단계;
상기 제4 엣지가 제거된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티에 포함되는 경우, 상기 제1 커뮤니티에서 엣지를 제거하는 것을 정지하는 단계; 및
상기 제3 엣지 및 상기 제4 엣지를 상기 제1 커뮤니티에서 제거함으로써 상기 제1 커뮤니티를 재구성하는 단계를 더 포함하는,
커뮤니티 재구성 방법.
삭제
제1항에 있어서,
상기 노드간의 유사도를 결정하는 단계는,
상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하는 단계; 및
상기 구별된 노드간의 유사도를 결정하는 단계를 포함하는 것을 특징으로 하는,
커뮤니티 재구성 방법.
제1 커뮤니티와 제2 커뮤니티를 포함하는 네트워크에서 커뮤니티를 재구성하기 위한 전자 장치에 있어서,
상기 네트워크를 구성하는 노드 간의 유사도를 결정하는 유사도 결정부;
상기 결정된 유사도에 기반하여 상기 제1 커뮤니티에 추가 또는 제거되어야 하는 엣지를 결정하는 엣지 결정부; 및
상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제1 엣지를 상기 제1 커뮤니티에 추가하고, 상기 제1 엣지가 추가된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티에 포함되는 경우, 상기 제1 커뮤니티에 추가하기로 결정된 엣지 중 하나인 제2 엣지를 상기 제1 커뮤니티에 추가하며, 상기 제2 엣지가 추가된 상기 제1 커뮤니티를 구성하는 엣지 중 상기 제1 커뮤니티를 벗어나는 엣지가 존재하는 경우, 상기 제1 커뮤니티로 엣지를 추가하는 것을 정지하고, 상기 제1 엣지 및 상기 제2 엣지를 상기 제1 커뮤니티에 추가함으로써 상기 제1 커뮤니티를 재구성하는 커뮤니티 재구성부;를 포함하는,
전자 장치.
제9항에 있어서,
상기 엣지 결정부는,
상기 결정된 유사도가 기설정된 제1 임계값을 초과하는 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에 추가되어야 하는 엣지로 판단하고, 상기 결정된 유사도가 기설정된 제2 임계값 미만인 노드간을 연결하는 엣지에 대해서는 상기 제1 커뮤니티에서 제거되어야 하는 엣지로 판단하는 것을 특징으로 하는,
전자 장치.
삭제
삭제
삭제
제9항에 있어서,
상기 커뮤니티 재구성부는,
상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제3 엣지를 상기 제1 커뮤니티에서 제거하고, 상기 제3 엣지가 제거된 상기 제1 커뮤니티를 구성하는 모든 엣지 중 상기 제1 커뮤니티를 벗어나는 엣지가 존재하는 경우, 상기 제1 커뮤니티에서 제거하기로 결정된 엣지 중 하나인 제4 엣지를 상기 제1 커뮤니티에서 제거하며, 상기 제4 엣지가 제거된 상기 제1 커뮤니티를 구성하는 모든 엣지가 상기 제1 커뮤니티에 포함되는 경우, 상기 제1 커뮤니티에서 엣지를 제거하는 것을 정지하고, 상기 제3 엣지 및 상기 제4 엣지를 상기 제1 커뮤니티에서 제거함으로써 상기 제1 커뮤니티를 재구성하는 것을 특징으로 하는,
전자 장치.
삭제
제9항에 있어서,
상기 유사도 결정부는,
상기 네트워크를 구성하는 노드 중에서 상기 제1 커뮤니티에 포함될 확률이 기설정된 제3 임계값을 초과하는 노드를 구별하고, 상기 구별된 노드간의 유사도를 결정하는 것을 특징으로 하는,
전자 장치.