중국어 속삭임(클러스터법
Chinese whispers (clustering method)
차이나 위스퍼는 네트워크 과학에서 사용되는 클러스터화 방식으로 유명한 위스퍼 [1]게임의 이름을 따왔다.클러스터링 방법은 기본적으로 특정 네트워크 내의 노드 또는 링크 커뮤니티를 식별하기 위해 사용됩니다.이 알고리즘은 2005년에 [1]Chris Biemann과 Sven Teresniak에 의해 설계되었다.이 이름은 노드가 동일한 유형의 정보를 [1]서로 전송하는 커뮤니티의 분리로 프로세스를 모델링할 수 있다는 사실에서 유래했습니다.
Chinese Whisper는 하드 파티셔닝, 랜덤화, 플랫 클러스터링([1]클러스터 간의 계층 관계 없음) 방식입니다.랜덤 속성은 같은 네트워크에서 프로세스를 여러 번 실행하면 다른 결과가 나오는 반면 하드 파티셔닝으로 인해 한 번에 하나의 노드만 하나의 클러스터에 속할 수 있음을 의미합니다.원래 알고리즘은 무방향, 가중치 및 가중치 없는 그래프에 적용할 수 있습니다.중국어 귓속말은 시간 선형이며,[1] 이는 네트워크에서 노드 및 링크 수가 매우 많아도 매우 빠르다는 것을 의미합니다.
알고리즘.
알고리즘은 무방향 무가중치 [1]그래프에서 다음과 같이 동작합니다.
- 모든 노드가 고유 클래스에 할당됩니다(초기 클래스의 수는 노드 수와 동일).
- 그런 다음 모든 네트워크 노드가 랜덤 순서로 하나씩 선택됩니다.모든 노드는 지정된 노드가 가장 많은 링크를 가진 클래스로 이동합니다.균등한 경우 군집은 균등하게 연결된 클래스에서 랜덤하게 선택됩니다.
- 2단계는 미리 정해진 횟수만큼 반복되거나 프로세스가 수렴될 때까지 반복됩니다.결국 이머징 클래스는 네트워크의 클러스터를 나타냅니다.
프로세스가 수렴되지 않을 수 있기 때문에 반복 횟수에 대한 미리 정해진 임계값이 필요합니다.한편, 약 10000개의 노드를 가지는 네트워크에서는,[1] 컨버전스가 없는 경우에서도, 클러스터는 40~50회의 반복 후에도 큰폭으로 변화하지 않습니다.
장점과 단점
중국인들의 속삭임의 가장 큰 강점은 시간 직선적 특성에 있다.처리 시간은 노드 수에 따라 선형적으로 증가하므로 알고리즘은 네트워크 내의 커뮤니티를 매우 빠르게 식별할 수 있습니다.이러한 이유로 중국어 속삭임은 노드 수가 매우 많은 그래프에서 커뮤니티 구조를 분석하는 데 좋은 도구입니다.네트워크의 월드 속성이 [1]작을 경우 메서드의 효율은 더욱 높아집니다.
한편, 작은 노드 번호의 경우 알고리즘이 결정적이지 않기 때문에 결과 클러스터는 종종 서로 크게 다릅니다.그 이유는 소규모 네트워크의 경우 어떤 노드에서 반복 프로세스를 시작하느냐가 더 중요하지만 대규모 네트워크에서는 시작점의 관련성이 [1]사라지기 때문입니다.따라서 작은 그래프의 경우 다른 클러스터링 방법을 사용하는 것이 좋습니다.
적용들
중국의 속삭임은 네트워크 과학의 많은 하위 분야에서 사용됩니다.가장 자주 언급되는 것은 자연어 처리 [2][3]문제의 맥락입니다.한편, 이 알고리즘은 네트워크 프레임워크와 관련된 모든 종류의 커뮤니티 식별 문제에 적용할 수 있습니다.중국어 귓속말은 네트워크 분석을 위해 설계된 오픈 소스 프로그램인 Gephi의[4] 확장 패키지로 개인적으로 사용할 수 있습니다.
레퍼런스
- ^ a b c d e f g h i Chris Biemann, "Chinese Whispers - 효율적인 그래프 클러스터링 알고리즘과 자연어 처리 문제에 대한 적용", 2006
- ^ Antonio Di Marco - Roberto Navigili, "그래프 기반 Word Sense Induction을 통한 웹 검색 결과 클러스터링 및 다양화", 2013
- ^ Ioannis Korkontzelos - 수레쉬 Manandhar, "다단어 표현에서의 구성성 검출", 2009
- ^ ""Gephi Marketplace"". Archived from the original on 2015-09-23. Retrieved 2015-06-02.
