Graphs are widely used for modeling various types of systems and information, including telephone communications, hyperlinks between web pages, and road networks. Many of such networks (i.e., graphs that model real-world systems and information) are growing, i.e., new nodes and edges appear over time.
Counting the instances of each graphlet (i.e., an induced subgraph isomorphism class) has been successful in characterizing local structures of networks, with numerous applications. While graphlets have been extended for analysis of growing networks, the extensions are designed for examining temporally-local subgraphs composed of edges with close arrival time, instead of long-term changes in local structures.
In this paper, as a new lens for growing network analysis, we study the evolution of distributions of graphlet instances over time in various networks at three different levels (graphs, nodes, and edges). At the graph level, we first discover that the evolution patterns are significantly different from those in random graphs. Then, we suggest a graphlet transition graph for measuring the similarity of the evolution patterns of graphs, and we find out a surprising similarity between the graphs from the same domain. At the node and edge levels, we demonstrate that the local structures around nodes and edges in their early stage provide a strong signal regarding their future importance. In particular, we significantly improve the predictability of the future importance of nodes and edges using the counts of the roles (a.k.a., orbits) that they take within graphlets.
그래프는 이메일 통신 및 온라인 커뮤니케이션 등 실제 세상의 다양한 유형의 상호 작용을 모델링하는 데 널리 사용된다. 실제 세상을 모델링하는 많은 그래프들은 시간이 지나면서 성장한다(시간이 지나면서 새로운 상호작용이 형성됨에 따라 새로운 간선이 생성되면서 크기가 커진다).
정적 그래프에서 그래프렛의 갯수를 분석하는 연구는 실제 세상 그래프의 지역적 구조를 특성화하는 데 성공했다. 이러한 접근 방식들은 시간 그래프를 분석하기 위해 확장되었지만, 지역적 구조의 장기적인 변화를 분석하기보다 가까운 시간 내에 도착한 간선으로 구성된 지역적 구조를 분석하도록 설계되었다.
본 논문에서는 네트워크의 성장을 분석하는 새로운 시각으로, 실제 세상 그래프에서 그래프렛 갯수의 분포 변화를 세 가지 다른 레벨(그래프, 정점, 간선)에서 연구한다. 먼저, 그래프 레벨에서 실제 세상 그래프의 진화 패턴이 랜덤 그래프의 패턴과 크게 다르다는 것을 발견한다. 또한, 실제 세상 그래프의 진화 패턴 유사성을 측정하기 위해 그래프렛 전환 그래프를 제안하고, 그래프렛 전환 그래프를 활용했을 때 동일한 도메인의 그래프들이 놀라운 유사성을 공유하고 있음을 발견한다. 이어서, 정점 및 간선 수준에서 초기 단계의 정점 및 간선 주변의 로컬 구조가 그들의 미래의 중요성에 대한 강력한 신호를 제공한다는 것을 발견한다. 특히, 우리는 그래프렛 내에서 정점과 간선이 그래프렛에 속한 역할의 수를 사용하여 정점과 간선의 미래의 중요성에 대한 예측 성능을 크게 향상시킨다.
