라벨 전파 알고리즘
Label propagation algorithm |
라벨 전파는 이전에 라벨이 부착되지 않은 데이터 포인트에 라벨을 할당하는 준감독 기계 학습 알고리즘이다.알고리즘을 시작할 때 데이터 포인트의 (일반적으로 작은) 부분 집합에는 라벨(또는 분류)이 있다.이러한 라벨은 알고리즘 과정 전체에 걸쳐 라벨이 부착되지 않은 점으로 전파된다.[1]
복잡한 네트워크 내에서, 실제 네트워크는 공동체 구조를 갖는 경향이 있다.라벨 전파는 커뮤니티를 찾기 위한 알고리즘이다.다른 알고리즘과[3] 비교하여 라벨 전파는 실행 시간과 네트워크 구조에 필요한 선행 정보의 양에 장점이 있다(사전 알 필요가 없다).단점은 독특한 해결책이 아니라 여러 해결책의 집합체를 만들어 낸다는 점이다.
알고리즘의 기능
초기 조건에서 노드에는 자신이 속한 커뮤니티를 나타내는 라벨이 부착된다.공동체 구성원 자격은 인접 노드가 소유하는 레이블에 따라 변경된다.이 변경은 노드의 1도 이내에서 라벨의 최대 개수에 따라 달라진다.모든 노드는 고유한 라벨로 초기화한 다음 라벨이 네트워크를 통해 확산된다.결과적으로, 밀접하게 연결된 그룹은 공통 라벨에 빠르게 도달한다.네트워크 전체에 이와 같이 밀도가 높은(공감) 집단이 많이 만들어지면, 그렇게 하는 것이 불가능할 때까지 계속 외부로 확장한다.[2]
이 프로세스에는 다음 5단계가 있다.[2]
1. 네트워크의 모든 노드에서 라벨을 초기화한다.지정된 노드 x의 경우 C(0x) = x.
2. t = 1을 설정한다.
3. 네트워크의 노드를 임의의 순서로 배열하여 X로 설정한다.
4. 그 특정한 순서로 선택된 각 x ∈ X에 대해, Cx(t) = f(Cxi1)(t), ...,Cxim(t),Cxi(m+1)(t - 1), ...,Cxik(t - 1)로 한다.여기서 이웃 간에 가장 높은 빈도로 발생하는 라벨을 반환한다.가장 높은 주파수 라벨이 여러 개 있는 경우 임의로 라벨을 선택하십시오.
5. 모든 노드에 인접 노드의 최대 수에 해당하는 레이블이 있으면 알고리즘을 중지한다.그렇지 않으면 t = t + 1을 설정하고 (3)로 이동한다.
다중 커뮤니티 구조
다른 알고리즘과 대조적으로 라벨 전파는 동일한 초기 조건에서 다양한 공동체 구조를 야기할 수 있다.일부 노드에는 예비 라벨이 부여되고 다른 노드에는 라벨이 부착되지 않은 상태로 유지되는 경우 솔루션의 범위를 좁힐 수 있다.따라서 라벨이 부착되지 않은 노드는 라벨이 부착된 노드에 더 잘 적응할 수 있을 것이다.공동체의 보다 정확한 발견을 위해, Jaccard의 지수는 모든 중요한 정보를 포함하는 다중 공동체 구조를 통합하는 데 사용된다.[2]
참조
- ^ Zhu, Xiaojin (2002). "Learning From Labeled and Unlabeled Data With Label Propagation". CiteSeerX 10.1.1.14.3864.
{{cite journal}}:Cite 저널은 필요로 한다.journal=(도움말) - ^ a b c d U.N. Raghavan – R. Albert – S. Kumara "대규모 네트워크에서 커뮤니티 구조를 탐지하는 거의 선형 시간 알고리즘", 2007년
- ^ M. E. J. Newman, "네트워크에서의 커뮤니티 구조 감지", 2004
