Graphs are widely used for modeling various types of interactions, such as email communications and online discussions. Many of such real-world graphs are temporal, and specifically, they grow over time with new nodes and edges. Counting the instances of each graphlet (i.e., an induced subgraph isomorphism class) has been successful in characterizing local structures of graphs, with many applications. While graphlets have been extended for temporal graphs, the extensions are designed for examining temporally-local subgraphs composed of edges with close arrival times, instead of long-term changes in local structures. In this paper, as a new lens for temporal graph analysis, we study the evolution of distributions of graphlet instances over time in real-world graphs 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.
翻译:图表被广泛用于模拟各种类型的互动, 如电子邮件通信和在线讨论。 许多这样的真实世界图形是时间性的, 具体地说, 它们随着时间而增长, 有新的节点和边缘。 计算每个图解( 即诱发的子图的偏向类) 成功地将图表的本地结构定性为多种应用。 虽然图时针的图解扩展了图解图解, 扩展图解是为了检查由接近时间的边缘组成的时间- 地方子图, 而不是地方结构的长期变化。 在本文中, 作为时间图分析的新镜头, 我们研究每个图解在现实世界图解的三个不同层次( 绘图、 节点和边缘) 。 在图形层面, 我们首先发现进化模式与随机图图的演变模式有很大不同。 然后我们建议一个图形转换图解图解图解用于测量图表进化模式的相似性, 并且我们从同一域的图表中找到一个惊人相似的相似性。 作为时间图解图解分析的新镜头, 我们研究图解在现实世界图解的分布过程的三个不同层次( 、 以及未来边缘的高度, 我们展示了它们具有强度, 的预 。 我们展示了它们的重要性。