Simplicial complexes are higher-order combinatorial structures which have been used to represent real-world complex systems. In this paper, we concentrate on the local patterns in simplicial complexes called simplets, a generalization of graphlets. We formulate the problem of counting simplets of a given size in a given simplicial complex. For this problem, we extend a sampling algorithm based on color coding from graphs to simplicial complexes, with essential technical novelty. We theoretically analyze our proposed algorithm named SC3, showing its correctness, unbiasedness, convergence, and time/space complexity. Through the extensive experiments on sixteen real-world datasets, we show the superiority of SC3 in terms of accuracy, speed, and scalability, compared to the baseline methods. Finally, we use the counts given by SC3 for simplicial complex analysis, especially for characterization, which is further used for simplicial complex clustering, where SC3 shows a strong ability of characterization with domain-based similarity.
그룹 상호작용을 나타낼 수 있는 모델링 방법으로는 하향 폐쇄 특성을 지닌 단체 복합체가 있다. 단체 복합체의 하위 복합체 중, 연결성을 지닌 개체를 심플렛라고 하는데, 꼭짓점 n개 위에서 정의된 심플렛을 “크기 n의 심플렛”이라고 일컫는다. 위 연구에서는, 단체 복합체에서 크기 4 이상의 심플렛을 세는 문제를 최초로 공식화하고, 이를 빠르지만 정확하게 셀 수 있는 “색상 코딩 기반 샘플링 알고리즘 SC3”을 제시, 그 수렴성과 비편향성을 이론적으로 뒷받침한다. 또한, 단순 복합체의 하위 패턴을 다루는 두 개의 베이스라인을 선정하여 SC3와 그 빠르기와 정확도를 비교한다. 심플렛 개수의 유용성을 보여주기 위해, 먼저 각 심플렛의 개수를 이용하여 이것의 중요도를 나타낼 수 있는 특성 프로파일을 정의한다. 다음으로는 실제 세계 단순 복합체 데이터셋 각각에 대응되는 특성 프로파일을 구한 후, 이메일, 학교, 공저자 등 같은 도메인의 특성 벡터들이 얼마나 유사한지 이것의 유사 행렬을 플롯하고 도메인 군집을 시행한다.
