A Hypergraph Approach for Estimating Growth Mechanisms of Complex Networks
A Hypergraph Approach for Estimating Growth Mechanisms of Complex Networks
复制标题
DOI：
10.1109/access.2022.3143612
复制
发表时间：
2022
期刊：
影响因子：
3.9
通讯作者：
M. Inoue;Thong Pham;Hidetoshi Shimodaira
中科院分区：
文献类型：
--
作者：
M. Inoue;Thong Pham;Hidetoshi Shimodaira
描述个体之间随时间的复杂交互的时间数据集在各个领域越来越常见。这样的数据集的传统图形表示可能导致信息丢失，因为在图形表示中，两个以上个体之间的高阶关系必须被分解成多个成对关系。在这些情况下，超图表示是优选的，因为它可以通过使用超边来保持高阶关系。然而，现有的时间复杂网络超图模型往往采用一些数据无关的增长机制，这是在大多数情况下的线性优先连接。原则上，这种预先规范是不可取的，因为它完全忽略了手头的数据。我们的工作提出了一个新的超图增长模型与数据驱动的优先连接机制估计从观察到的数据。我们的方法的一个关键组成部分是一个递归公式，使我们能够克服在计算模型中的归一化因子的瓶颈。我们还处理了一个经常被忽视的选择偏差，在建模新的边缘与新节点的出现。拟合建议的超图模型，以13个现实世界的数据集，从不同的领域，我们发现，所有估计的偏好连接函数偏离了很大程度上从线性形式。这表明需要废除线性偏好依恋假设并采用数据驱动的方法。我们还表明，我们的模型在复制这些真实世界数据集中观察到的一阶和二阶结构方面优于传统模型。
Temporal datasets that describe complex interactions between individuals over time are increasingly common in various domains. Conventional graph representations of such datasets may lead to information loss since higher-order relationships between more than two individuals must be broken into multiple pairwise relationships in graph representations. In those cases, a hypergraph representation is preferable since it can preserve higher-order relationships by using hyperedges. However, existing hypergraph models of temporal complex networks often employ some data-independent growth mechanism, which is the linear preferential attachment in most cases. In principle, this pre-specification is undesirable since it completely ignores the data at hand. Our work proposes a new hypergraph growth model with a data-driven preferential attachment mechanism estimated from observed data. A key component of our method is a recursive formula that allows us to overcome a bottleneck in computing the normalizing factors in our model. We also treat an often-neglected selection bias in modeling the emergence of new edges with new nodes. Fitting the proposed hypergraph model to 13 real-world datasets from diverse domains, we found that all estimated preferential attachment functions deviates substantially from the linear form. This demonstrates the need of doing away with the linear preferential attachment assumption and adopting a data-driven approach. We also showed that our model outperformed conventional models in replicating the observed first-order and second-order structures in these real-world datasets.