Percolation transitions in growing networks and simplicial complexes

Abstract

Percolation theory can explain the formation of a giant cluster in a system. About a decade ago, various types of local suppression rules were proposed to alter the transition types into explosive percolation (EP) transitions and these rules suppress the growth of larger clusters but support those of smaller ones. When the growth of the large cluster is locally suppressed in static networks whose total number of nodes in the system is fixed, explosive percolating behavior of the order parameter, which is the giant cluster size, can be observed but it remains continuous not discontinuous. However, the types of percolation transitions in static networks become hybrid when the growth of the large cluster is globally suppressed. In the real world, the system grows and we thus consider the growing network where the total number of nodes in the system increases with time. To investigate the properties of EP transitions in these types of systems, we first derive the rate equation of the size distribution for various models. Our findings confirm that the order parameter exhibits the second-order phase transition under the local suppression rule, but the first-order phase transition under the global suppression rule. More realistically, considering that multi-body interactions in the real world can be explained by simplexes and degree distribution is scale free, we extend the growing networks to the growing scale-free simplicial complexes (GSFSC). In GSFSC under the suppression rules, the transition types are similar to those of the case of networks. Finally, we investigate the features of the percolation variables using supervised and unsupervised machine learning approach. Especially we confirm that features of parent node number and occupation number configurations are the giant cluster sizes and occupation probabilities, respectively, in the two-dimensional bond (site) percolation. Based on these results, we learned successfully classification and regression machines in networks by using supervised learning analysis. This work helps to understand the properties in general growing system and revealed that the machine learning approach is applicable to networks as well as lattices.

여과 이론은 주어진 계에서 대형 클러스터의 형성을 설명한다. 모든 클러스터들이 무작위로 연결되며 성장할 경우 계의 구조에 관계없이 임계점에서 연속적으로 대형 클러스터가 나타난다. 이러한 무작위성만으로는 폭발적 여과 상전이의 특성을 설명할 수 없기 때문에, 지난 십여 년간 여과상전이의 종류를 폭발적 여과 상전이로 바꾸기 위하여 작은 클러스터의 성장을 촉진하고 큰 클러스터의 성장은 방해하는 다양한 국소적 억제 규칙이 제시되어왔다. 전체 노드의 개수가 일정한 정적 네트워크에서 큰 클러스터의 성장이 국소적으로 억제되면, 대형 클러스터가 매우 폭발적으로 나타나지만 그 과정이 불연속적이지 않고 연속적이다. 이때 모든 노드들의 정보를 전역적으로 이용하여 큰 클러스터의 성장을 억제하면, 대형 클러스터가 임계점에서 완전히 불연속적으로 나타나게 된다. 하지만 실제 세상에서는 시스템이 성장하는 경우가 많으므로 본 연구에서는 시간에 따라 노드가 증가하는 성장 네트워크에 억제 규칙이 적용되는 경우를 고려하였다. 다양한 종류의 모델에 대하여 클러스터 크기 분포에 대한 비율 방정식을 세우고 이로부터 해석적으로 상전이의 종류를 조사해본 결과, 국소적 억제 조건하에서는 2차 상전이의 특징이 나타나고 전역적 억제 조건 하에서는 1차 상전이의 특징이 나타났다. 이때 성장 네트워크에 국소적 억제 규칙이 적용되었을 경우 기존에 존재하던 노드들이 링크로 연결될 후보군으로 선택될 확률이 높기 때문에 정적 네트워크에서보다 대형 클러스터가 좀 더 부드럽게 나타남을 확인하였다. 또한 전역적인 억제 규칙이 적용되었을 경우에는 무한차 상전이에서의 특징과 유사하게 대형 클러스터가 생기기 전 클러스터 크기 분포가 지수함수를 따르는 임계 영역이 존재함을 확인할 수 있었다. 다음으로, 더 나아가 실제 세계의 도수 분포가 척도가 없고 두 개체 이상이 서로 상호작용한다는 특징에 기반하여 성장 네트워크를 척도 없는 성장 단체 복합체로 확장하였다. 척도 없는 성장 단체 복합체가 억제 규칙 하에서 성장할 때 나타나는 상전이의 종류는 네트워크에서의 경우와 동일함을 확인하였다. 마지막으로, 지도 및 비지도 기계학습 방법을 이용하여 여과 상전이를 기술하는 물리 변수들의 특성을 조사하였다. 그 결과 부모 노드 숫자와 점유 숫자 구성 집합들의 대표 특성이 각각 대형 클러스터의 크기와 점유 확률임을 알 수 있었고, 이러한 성질을 이용해서 네트워크에서의 여과상전이 또한 성공적으로 지도학습하였다. 결과적으로, 본 연구는 일반적인 성장하는 시스템을 해석적으로 이해하는 데 도움을 줄 수 있으며, 기계학습 방법이 격자뿐만 아니라 네트워크에도 성공적으로 적용될 수 있음을 보여준다.