Estimating the Size of a Large Network and its Communities from a Random Sample
원문 초록
Most real-world networks are too large to be measured or studied directly and there is substantial interest in estimating global network properties from smaller sub-samples. One of the most important global properties is the number of vertices/nodes in the network. Estimating the number of vertices in a large network is a major challenge in computer science, epidemiology, demography, and intelligence analysis. In this paper we consider a population random graph G = (V;E) from the stochastic block model (SBM) with K communities/blocks. A sample is obtained by randomly choosing a subset W and letting G(W) be the induced subgraph in G of the vertices in W. In addition to G(W), we observe the total degree of each sampled vertex and its block membership. Given this partial information, we propose an efficient PopULation Size Estimation algorithm, called PULSE, that correctly estimates the size of the whole population as well as the size of each community. To support our theoretical analysis, we perform an exhaustive set of experiments to study the effects of sample size, K, and SBM model parameters on the accuracy of the estimates. The experimental results also demonstrate that PULSE significantly outperforms a widely-used method called the network scale-up estimator in a wide variety of scenarios. We conclude with extensions and directions for future work.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
MSGNN: 새로운 자기 부호 라플라시안 기반의 스펙트럼 그래프 신경망
MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian
부호가 있고 방향성이 있는 네트워크는 실제 응용 분야 도처에 존재합니다. 그러나 이러한 네트워크를 위한 스펙트럼 그래프 신경망(GNN)을 제안한 연구는 비교적 적었습니다. 본 논문에서는 부호 그래프에서의 부호 라플라시안과 방향성 그래프에서의 자기 라플라시안(magnetic Laplacian)을 자연스럽게 일반화한, 자기 부호 라플라시안(magnetic signed Laplacian)이라 부르는 부호 방향 라플라시안 행렬을 도입합니다. 이어 이 행렬을 사용하여 새로운 효율적인 스펙트럼 GNN 아키텍처를 구축하고, 노드(node) 클러스터링 및 링크 예측 태스크 모두에서 광범위한 실험을 수행합니다. 이 실험들에서는 부호 정보 관련 태스크, 방향 정보 관련 태스크, 그리고 부호 및 방향 정보 모두와 관련된 태스크를 다룹니다. 제안된 스펙트럼 GNN이 부호 및 방향 정보를 모두 반영하는 데 효과적이며 광범위한 데이터셋에서 최고 수준의 성능을 달성함을 입증합니다. 추가로, 부호 방향 확률적 블록 모델(Signed Directed Stochastic Block Model)이라 부르는 새로운 합성 네트워크 모델(model)과 금융 시계열의 리드-래그(lead-lag) 관계에 기반한 다수의 새로운 실제 데이터셋을 제공합니다.
인과 데이터 융합에서의 군집화와 가지치기
Clustering and Pruning in Causal Data Fusion
데이터 융합(data fusion)은 관측 데이터(observational data)와 실험 데이터(experimental data)를 결합하는 과정으로, 그렇지 않았다면 식별 불가능(non-identifiable)했을 인과 효과(causal effects)의 식별을 가능하게 할 수 있습니다. 특정 시나리오에 대한 식별 알고리즘들이 개발되었지만, 특히 변수가 일부 데이터 소스(data sources)에는 존재하고 다른 곳에는 없는 경우, do-calculus는 인과 데이터 융합을 위한 유일한 범용 도구로 남아 있습니다. 그러나 do-calculus에 기반한 접근 방식은 변수의 수가 증가하고 인과 그래프(causal graph)가 복잡해짐에 따라 계산적 어려움에 직면할 수 있습니다. 결과적으로, 핵심 특징(essential features)을 보존하면서 이러한 모델의 크기를 줄일 필요가 있습니다. 이를 위해, 본 연구는 인과 데이터 융합을 위한 전처리 연산으로 가지치기(pruning, 불필요한 변수 제거)와 군집화(clustering, 변수 결합)를 제안합니다. 단일 데이터 소스(single data source)에 대한 기존 결과를 일반화하고, 다중 데이터 소스(multiple data sources)의 경우 가지치기와 군집화를 적용하기 위한 조건을 도출합니다. 더 작은 그래프를 기반으로 더 큰 그래프에서 인과 효과의 식별 가능성(identifiability) 또는 식별 불가능성(non-identifiability)을 추론하기 위한 충분 조건(sufficient conditions)을 제공하고, 식별 가능한 인과 효과에 대해 해당 식별 함수(identifying functional)를 구하는 방법을 제시합니다. 역학(epidemiology) 및 사회과학(social science)의 예시를 통해 연구 결과의 활용성을 입증합니다.
베이지안 회귀, 트리 앙상블 및 Shapley 값을 통합한 역학 데이터의 비선형성을 넘어선 발견과 추론
Discovery and inference beyond linearity for epidemiological data by integrating Bayesian regression, tree ensembles and Shapley values
머신러닝(ML)은 가설 없는(hypothesis-free) 위험 및 보호 요인 발견을 위해 역학 및 의료 연구에서 인기를 얻고 있습니다. ML은 비선형성과 상호작용을 발견하는 데 강점이 있지만, 신뢰할 수 있는 추론(inference)의 부재로 인해 이러한 강점이 저해됩니다. Shapley 값은 특징의 효과에 대한 국소적 측정치를 제공하지만, 이러한 효과에 대한 타당한 불확실성 정량화가 일반적으로 부족하여 통계적 추론을 불가능하게 만듭니다. 우리는 이러한 한계를 해결하기 위해 전용 베이지안 희소 회귀 모델(model)과 개선된 트리 기반 규칙 생성기, 그리고 Shapley 값 귀속을 결합한 RuleSHAP 프레임워크를 제안합니다. RuleSHAP는 비선형 및 상호작용 효과의 탐지를 제공하며, 개별 수준에서의 불확실성 정량화를 핵심 기여로 포함합니다. 우리는 이 프레임워크 내에서 한계 Shapley 값을 계산하기 위한 효율적인 공식을 유도합니다. 우리는 고콜레스테롤혈증과 고혈압에 대한 여러 효과를 탐지하고 추론하기 위해 역학 코호트 데이터에 RuleSHAP를 적용했으며, 여기에는 연령, 성별, 인종, BMI 및 포도당 수준과 같은 특징 간의 비선형 상호작용 효과가 포함됩니다. 결론적으로, 우리는 시뮬레이션 데이터를 통해 프레임워크의 타당성을 입증합니다.
A Simple Approximate Bayesian Inference Neural Surrogate for Stochastic Petri Net Models
Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening
Structural-Temporal Coupling Anomaly Detection with Dynamic Graph Transformer
토론
이 논문과 연결된 포럼 글이 아직 없습니다.