Graph Isomorphism Problem 图同构问题

图同构问题是图匹配问题的基础，也是目前介于P于NP之间的一个有趣问题。相关研究旨在解决能否在多项式时间内判断两个网络是否同构，即具有完全相同的网络结构的问题。 该问题的背景可以参考 The graph isomorphism disease. 该问题在理论研究工作中经久不衰，如最近的 On the equivalence between graph isomorphism testing and function approximation with GNNs 探讨了图同构问题和函数逼近问题的等价性。

其他可供参考的文献：
On convex relaxation of graph isomorphism
Improved random graph isomorphism

Social Network De-anonymization Problem 社交网络去匿名问题

去匿名问题是图匹配问题的一种，它有时也被称为网络对齐（Network Alignment）问题。相关研究旨在更快、更精准地将不同网络中的结点进行匹配。从理论角度出发，可以探讨网络在何种条件下可以完全匹配，比如 on the privacy of anonymized networks 分析了随机网络完全匹配需要满足的条件；从算法角度出发，也有大量工作进行了推导与计算，参考A Short Survey of Recent Advances in Graph Matching.

其他可供参考的文献：
On the Performance of a Canonical Labeling for Matching Correlated Erdős-Rényi Graphs
Seeded Graph Matching: Efficient Algorithms and Theoretical Guarantees
Poor Textural Image Matching Based on Graph Theory
Typicality Matching for Pairs of Correlated Graphs
De-anonymizing Social Networks with Overlapping Community Structure
De-anonymization of Social Networks: the Power of Collectiveness

Graph Percolation Problem 图渗流问题

渗流是指流体在孔隙介质中的流动，图的渗流简单来说可以理解为图中结点相互连通。图渗流问题研究的就是网络的稳定性和连通性问题，这也是目前网络科学领域的热门研究话题。本领域的一篇开创性工作是2010年发表在Nature上的 Catastrophic cascadng of failures in interdependent networks，更详细的介绍也可以参考On percolation in random graphs with given vertex degrees. 渗流理论作为一种工具对多层网络的稳定性研究工作提供了很大帮助，如 Percolation Theory on Interdependent Networks Based on Epidemic Spreading 等对此进行了详细分析。同时，根据定义的不同，渗流也分为 k-core percolation, bootstrap percolation, explosive percolation等等。它们在各个不同的领域也发挥着重要作用。

常用复杂网络数据集网站集合：
https://www.jianshu.com/p/9313bc75c94b