Source-linked AI summary
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
Peter J. Mucha, Thomas Richardson, Kevin Macon, Mason A. Porter, Jukka-Pekka Onnela
TL;DR
Community detection에는 multislice network를 위한 일반적 framework가 부족하다. 이 논문은 stacked slices와 identity arcs를 사용해 quality function을 개발하고, temporal·multiplex·multiscale setting 전반으로 modularity 기반 분석을 확장한다.
문제
Community detection에는 여러 slice, link type, scale에 걸친 network를 표현하는 방법이 필요하다.
방법
이 논문은 identity arc로 연결된 stacked slice로 표현되는 multislice network를 위한 generalized quality function을 개발한다.
결과
이 framework는 multislice network로 modularity를 확장하고, quality를 최적화하는 community partition의 특성을 규명한다.
시사점 및 한계
이 framework는 시간에 따라 진화하거나 여러 link type을 포함하거나 여러 scale에 걸쳐 있는 network의 community structure 분석을 지원한다.
시사점 및 한계
이 분석에는 independence assumption이 포함되며, 한 최적화 논증에서는 일반성을 잃지 않고 partition이 유일하게 지정된다고 가정한다.
Abstract
from arXiv · showhide
Network science is an interdisciplinary endeavor, with methods and applications drawn from across the natural, social, and information sciences. A prominent problem in network science is the algorithmic detection of tightly-connected groups of nodes known as communities. We developed a generalized framework of network quality functions that allowed us to study the community structure of arbitrary multislice networks, which are combinations of individual networks coupled through links that connect each node in one network slice to itself in other slices. This framework allows one to study community structure in a very general setting encompassing networks that evolve over time, have multiple types of links (multiplexity), and have multiple scales.
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks를 위한 Supporting Online Material
Supporting material은 normalized Laplacian dynamics에서 bipartite, directed, signed, multislice networks로 framework를 확장하며, parameter-linear quality functions에 대한 partition-optimization domain의 convexity를 증명한다.
- Framework 일반화: framework는 normalized Laplacian dynamics에서 bipartite, directed, signed, multislice networks로 null model을 일반화한다.Multislice networks는 slice 간 대응하는 node를 연결하며, identity arc는 dynamic graph에 대한 measure의 시각화와 확장을 지원한다.
- Community-detection 방법론: Multislice networks에서 community detection은 normalized Laplacian dynamics 아래의 community stability에서 도출되며, unnormalized dynamics에 기반한 병렬 분석도 제시한다.
- Optimization 특성: quality function이 해당 parameter에 대해 linear일 때 각 network partition의 optimization domain은 parameter space에서 convex하다.Supporting material은 이 convexity 결과가 가져올 수 있는 결과도 논의한다.
Laplacian Dynamics 형식론
Laplacian dynamics 형식론은 random walk가 독립적인 경우에 비해 커뮤니티 내부에 머무르는 지속성을 통해 커뮤니티 안정성을 정의하며, 이에 따라 시간 의존적 quality function을 도출한다. 그 일차 근사는 t = 1에서 Newman-Girvan modularity를 복원하고 resolution parameter를 γ = 1/t로 해석한다 (13).
- Modularity 연결: t = 1에서 도출된 quality function은 Newman-Girvan modularity로 환원되며, 더 일반적인 형태는 resolution parameter를 포함하는 표준 Potts 일반화에 해당한다 (13).이 framework는 continuous-time dynamics에서 modularity를 도출하고, 여러 timescale에 걸쳐 그 해석을 확장한다.
- Stability 정의: Community stability R(t)는 stationary random walker가 시간 t 후에도 동일한 커뮤니티에 남아 있을 확률이 독립성 가정에서 예상되는 확률보다 높은지를 측정한다 (13).이 dynamics는 L_ij = A_ij/k_j − δ_ij를 사용하며, independence 기여는 null-model 항에 나타난다.
- 품질 함수 유도: e^(tL)를 일차까지 전개하면 R(t)는 커뮤니티 품질 함수를 도출하며, 최적화하는 분할에 영향을 주지 않는 δ_ij 항은 제외된다 (13).근사는 (e^tL)_ij ≈ δ_ij + tL_ij이다.
- Resolution 해석: quality function을 t로 나누어도 고정된 t에서 최적해는 보존되며, resolution parameter는 γ = 1/t (13)이라는 직접적인 해석을 갖는다.따라서 resolution은 dynamical time의 역수로 해석된다.
일반화된 Laplacian Dynamics
이 framework는 connection type에 null model을 조건화하여 Laplacian-dynamics community detection을 일반화하며, multiple link type, spreading weight, multislice structure를 허용한다. 적절한 bipartite, directed, signed-network null model을 복원하고 원리적인 multislice modularity를 도출한다.
- 단일 slice null model: resolution parameter γ를 도입하여 bipartite 및 directed network의 generalized null model을 복원한다.bipartite 결과는 γ = 1 Barber null model을 일반화하고, directed 결과는 표준 γ = 1 directed null model을 확장한다.
- Multiple connection type: 이 방법은 bidirectional directed motion과 incoming edge와 outgoing edge를 구분하는 conditional probability를 포함하여 Laplacian dynamics를 multiple connection type으로 확장한다.이는 motion을 link direction으로 제한한 Lambiotte et al. (13)과 대조된다.
- 부호 네트워크: 부호 네트워크 동역학은 양의 링크와 음의 링크에 대한 null model을 생성하며, 서로 다른 resolution parameter γ+와 γ−를 사용한다.이 구성은 γ = 1에서 제안된 signed null model 하나로 환원되며, 더 일반적인 signed model의 특수한 경우다.
- 유연한 Spreading Weight: 세 번째 일반화는 link type별로 different spreading weight를 허용하여 undirected signed model을 도출하고, 앞선 확장과 결합하면 그 directed version도 도출한다.이러한 유연성은 상대적인 edge strength에만 의존하지 않고 conditional probability를 별도로 reweight할 수 있게 한다.
- Multislice network: Multislice network에서 이 framework는 intra-slice edge와 inter-slice coupling을 결합하고 두 step type 모두에 대한 conditional probability를 사용하여 modularity를 도출한다.이 formulation은 각 slice에서 서로 다른 resolution γs를 허용하며, multislice network로 modularity를 일반화하는 원리적 방법으로 제시된다.
비정규화 Multislice Laplacian Dynamics
이 framework는 structure-constrained independent probabilities를 사용해 standard Laplacian dynamics에서 도출된 uniform-random-graph quality function을 multislice networks로 일반화한다. Quality function은 ω → 0에서 서로 독립적인 slice partition을, ω ≫ 1에서 slice averaging을 산출한다.
- Null model 일반화: Multislice extension은 network의 multislice structure에 의해 제약되는 natural independent probabilities를 사용해 uniform random null model (5)을 일반화한다.이는 Lambiotte et al. (13)의 standard-Laplacian community-stability analysis를 기반으로 한다.
- Dynamics: Standard multislice Laplacian은 constant steady-state distribution jr = 1/N을 가지며, node-departure rate는 multislice strength κjr에 비례한다.여기서 N은 slice 전체에 걸친 총 node 수이고, κjr = kjr + cjr이다.
- Quality-function construction: 이 construction은 slice 내부와 slice 간에 서로 다른 resolution parameter를 허용하고, inter-slice coupling strength를 binary Cjsr = {0, ω} 값에 흡수한다.Coupling 간 weight를 다르게 설정할 수도 있으며, diagonal δijδsr 항은 optimal partition에 영향을 주지 않는다.
- Limiting behavior: ω → 0에서는 quality function이 각 slice를 독립적으로 partition하는 반면, ω ≫ 1에서는 summed constant contribution을 통해 slice averaging이 이루어진다.Contribution이 constant이므로, 여기서 large-coupling behavior는 normalized Laplacian dynamics의 경우보다 단순하다.
볼록 최적화 영역
매개변수에 선형인 quality function에서는 각 partition의 최적화 영역이 반드시 볼록이어야 한다. 두 parameter point에서 최적이면 이를 잇는 선분 전체에서도 최적이어야 한다는 뜻이다. 이 결과는 multislice network를 넘어 일반화되며, 불충분한 최적화를 탐지하는 진단 기준을 제공한다.
- 볼록성 정리: resolution parameter와 coupling parameter에 대한 선형성은 개별 partition의 볼록 최적화 영역을 요구하며, 모든 선형 community-detection quality function에도 적용된다.이 결과는 generalized multislice quality function에 적용되며, 더 넓게는 parameter에 선형인 quality function에도 적용된다.
- 볼록성 정리: 하나의 partition이 두 parameter point에서 최적이면, 두 점을 잇는 선분 전체에서 계속 최적이어야 한다.이는 두 endpoint에서 서로 다른 partition에 대한 quality inequality를 비교하면 따른다.
- 증명의 귀결: 연결 선분을 넘어 한 endpoint에서 선호된 partition은 그에 대응하는 연장 구간을 따라 반드시 더 높은 quality를 갖지만, 해당 구간에서 어느 partition도 최적일 필요는 없다.따라서 명시된 선형 형식의 quality function에서는 비볼록 최적화 영역이 허용되지 않는다.
예시
이 절에서는 본문에서 논의한 세 가지 예시에 대한 추가 세부사항을 제시한다.
- 본문에서 논의한 세 가지 예시에 대한 추가 세부사항을 제시한다.
다중 스케일에 걸친 커뮤니티 탐지
Multislice 커뮤니티 탐지는 Zachary Karate Club network에서 16개 resolution scale에 걸친 커뮤니티 구조를 동시에 추적했다. 인접한 slice 간 coupling이 증가할수록 커뮤니티가 인접 scale에 걸쳐 확장되어 multiscale 발달을 체계적으로 추적할 수 있었다.
- Multiscale coupling: 인접한 resolution slice 간 coupling이 증가할수록 커뮤니티가 여러 scale에 걸쳐 걸쳐 있었으며, coupling이 임의로 커지면 전체 resolution 범위에 걸쳐 확장되었다.slice 간에는 resolution만 변하는 경우, infinite-coupling limit은 평균 γ_s≈2.125에서의 단일-resolution 탐지에 해당했다.
시간 의존 네트워크에서의 커뮤니티 탐지
Multislice 커뮤니티 탐지를 110개의 상원 투표 네트워크 슬라이스에 적용한 결과, 독립적인 의회 분할을 넘어 시간에 따른 개인 및 집단 투표 동태가 드러났다. 도출된 9개 커뮤니티 구조는 미국 정치에서 역사적으로 중요한 전환점을 부각했다.
- 시간 의존 네트워크에서의 커뮤니티 탐지: 각 2년 임기의 의회는 투표 유사도에 기반한 상원의원 쌍의 가중치로 네트워크 슬라이스를 구성했으며, 인접한 슬라이스는 두 의회에서 모두 재임한 상원의원들이 있을 때만 서로 연결되었다.이 정식화는 슬라이스에 따라 링크 강도와 노드 집합이 모두 변할 수 있게 했다.
- 시간 의존 네트워크에서의 커뮤니티 탐지: Multislice 탐지는 110개의 독립적인 의회 분할의 합집합으로는 포착되지 않았던 시간에 따른 개인 및 집단 투표 동태를 밝혀냈다.분석에는 일반화된 Louvain 알고리즘과 슬라이스 간 결합 ω = 0.5를 적용한 KL 단계가 사용되었다.
- 시간 의존 네트워크에서의 커뮤니티 탐지: 더 충실한 정치 연구에서는 슬라이스 간 결합 강도 ω가 변함에 따라 탐지된 커뮤니티 구조가 어떻게 달라지는지를 체계적으로 검토해야 한다.보고된 분할에는 ω = 0.5가 사용되었다.
Multiplex 네트워크의 커뮤니티 탐지 · 보충 참고문헌
Multislice 커뮤니티 탐지를 1,640명의 학생으로 구성된 4-layer social multiplex에 적용하여, coupling strength가 개인에게 별도의 커뮤니티 할당을 부여할지 공유된 커뮤니티 할당을 부여할지를 어떻게 좌우하는지 밝혔다. 이 framework는 layer 간 역할 비교도 지원하며, layer-specific assignment를 통해 overlapping community를 나타낸다 [2,3,S6].
- Multiplex 네트워크의 커뮤니티 탐지: 이 multiplex는 대학 첫해 동안 1,640명의 학생 사이에서 관찰된 Facebook friendship, picture friendship, shared-roommate tie, housing-group preference로 구성되었다.데이터는 미국 북동부의 한 익명 대학에서 수집되었다 [24].
- Multiplex 네트워크의 커뮤니티 탐지: Tie type이 범주형이었으므로 각 학생은 인접한 ordered slice에만 연결된 것이 아니라 4개 layer 모두에서 자기 자신과 coupling되었다.따라서 이 inter-slice coupling은 인접한 network slice만 연결하는 coupling과 다르다.
- Multiplex 네트워크의 커뮤니티 탐지: Coupling strength가 증가할수록 connection pattern이 상대적으로 유사한 layer 사이에서 커뮤니티가 가장 두드러지게 통합되었다.Table 1은 4개 layer 전체의 총 커뮤니티 수와 1, 2, 3, 4개 커뮤니티에 할당된 개인의 비율을 요약한다.
- Multiplex 네트워크의 커뮤니티 탐지: ω ∈[0.2, 0.5]에서는 상당한 다수의 개인이 1개 또는 2개 커뮤니티에만 속했으며, 이는 connection type 전반에서 group-level similarity가 있음을 나타낸다.추가로 상당한 수의 개인은 3개 커뮤니티에 속했고, 소수만이 4개 할당을 유지했으며, 이는 layer 간 위치가 뚜렷하게 다름을 나타낸다.
- Multiplex 네트워크의 커뮤니티 탐지: Layer별로 서로 다른 할당은 각 network와 complete multislice network에서 개인의 역할을 비교하는 데 도움이 될 수 있다.각 layer-specific node의 hard partition은 한 개인이 서로 다른 appearance에서 서로 다른 커뮤니티에 속하는 것을 여전히 허용한다.
- 보충 참고문헌: Multiplexity는 커뮤니티의 overlap을 허용하는 방법의 필요성을 제기한다 [2,3,S6].Layer-specific community assignment는 개인의 appearance마다 membership이 다르게 나타나도록 하여 이러한 overlap을 표현하는 메커니즘을 제공한다.