🧐 Community detection algorithms
네트워크에서 다른 집단 보다 좀 더 밀집하게 묶여있는, 다시 말해 모듈성(modularity)이 높은 집단을 community라고 부른다. Community detection 알고리즘은 전체 집단에 어떤 커뮤니티가 있고, 또 이러한 커뮤니티는 어떤 특성을 가지고 있는지를 분석하는 방법이다.
1. Louvain
Louvain 알고리즘은 Community detection의 한 방법으로, 관계 밀도를 적절하게 정의된 랜덤 네트워크와 비교하여 커뮤니티의 품질을 측정한다.
-
Phase1: 한 노드를 인접한 다른 커뮤니티에 배치하여 모듈성을 측정한다. 모듈성이 커지는 커뮤니티가 있으면 해당 노드는 그 커뮤니티에 속한다. 모듈성이 가장 높아질 때까지 반복한다.
-
Phase2: Phase1에서 생성된 커뮤니티를 가지고 새로운 커뮤니티를 생성한다. 기존 커뮤니티 간에 연결되어있던 link weight는 합쳐서 하나의 link로 생성하고, 새로운 커뮤니티의 노드들 간의 link는 self-loop로 대체한다.
모듈성이 더이상 증가하지 않을 때까지 Pass(Phase1 + Phase2)를 반복한다.
2. Label Propagation Algorithm(LPA)
LPA는 네트워크 구조만을 사용하여 커뮤니티를 찾아내는 빠른 알고리즘이다. 내가 속한 커뮤니티는 나의 주변 사람들이 속한 커뮤니티일 확률이 높다는 직관적인 관점에서 출발한다.
모든 노드는 각자 유일한 label을 가진다. 노드의 순서가 랜덤하게 배치된 리스트를 작성하고, 해당 노드의 주변 노드들이 지닌 label 중 가장 빈도가 높은 label로 해당 노드의 label을 변경한다. 모든 노드가 가장 높은 빈도의 label을 가질 때까지 반복한다.
🙉 Practice in Neo4j!
2-1) 데이터 생성
CREATE
(alice:User {name: 'Alice', seed_label: 52}),
(bridget:User {name: 'Bridget', seed_label: 21}),
(charles:User {name: 'Charles', seed_label: 43}),
(doug:User {name: 'Doug', seed_label: 21}),
(mark:User {name: 'Mark', seed_label: 19}),
(michael:User {name: 'Michael', seed_label: 52}),
(alice)-[:FOLLOW {weight: 1}]->(bridget),
(alice)-[:FOLLOW {weight: 10}]->(charles),
(mark)-[:FOLLOW {weight: 1}]->(doug),
(bridget)-[:FOLLOW {weight: 1}]->(michael),
(doug)-[:FOLLOW {weight: 1}]->(mark),
(michael)-[:FOLLOW {weight: 1}]->(alice),
(alice)-[:FOLLOW {weight: 1}]->(michael),
(bridget)-[:FOLLOW {weight: 1}]->(alice),
(michael)-[:FOLLOW {weight: 1}]->(bridget),
(charles)-[:FOLLOW {weight: 1}]->(doug)2-2) Louvain 결과
CALL gds.louvain.stream({nodeProjection:'User', relationshipProjection:'FOLLOW'})
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name
2-3) LPA 결과
CALL gds.labelPropagation.stream({nodeProjection:'User', relationshipProjection:'FOLLOW'})
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name
