Growing Hypergraphs with Homophily
本文引入了一种用于生长型超图的机制模型，该模型通过引入同质性驱动的边复制过程，放宽了边独立性的假设，从而实现了幂律度分布、通过期望最大化进行参数估计，并提升了复杂多体系统的社区检测性能。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，你正试图理解一场规模宏大、混乱不堪的派对是如何演变的。在科学领域，这就是对网络的研究。通常，科学家们将这些网络视为两个个体之间简单的连接——就像爱丽丝和鲍勃之间的一次电话通话。这被称为“二元”（dyadic）交互。但现实生活更加复杂。有时，一群朋友会聚在一起，或者一个五人委员会同时签署一项法案。这些是“超图”（hypergraphs），其中一个连接（一条边）可以同时链接三个人、四个人甚至数十个人。
长期以来，计算机科学家一直试图构建计算机模型来预测这些群体是如何形成的。一个流行的概念是同质性（homophily），这只是一个高级词汇，意为“物以类聚”。它是指具有相似特征的人（比如穿着相同的乐队 T 恤或投给同一个政党）倾向于聚在一起的现象。大多数旧模型假设每一个新群体的形成都是完全独立的，就像为每一次新的派对都重新掷一次全新的骰子。他们认为之前的群体不会影响下一个群体。但在现实生活中，群体往往是之前群体的回响。如果你看到一群朋友，他们下一次形成的群体很可能包含一些相同的人，或者至少是与他们非常相似的人。本文提出了一个问题：如果我们不再假装每个新群体都是随机的骰子点数，而是假设新群体是旧群体的混乱、带有噪声的复制品，会发生什么？
本文作者 Violet Ross、Francis Cataldo 和 Philip S. Chodrow 引入了一种名为 CHILI（受标签交互影响的复制超边）的新型计算机模型。把 CHILI 想象成一个生长超图的配方，一次一个群体。在他们的模拟中，一个新群体并不会凭空出现。相反，计算机选取一个现有的群体（“种子”）并尝试复制它。但这是一个带有噪声的复制。原始群体中的某些成员会被邀请加入新群体，而另一些则会被留下。至关重要的是，邀请某人的决定取决于他们的“标签”——比如他们是民主党人还是共和党人，或者是男孩还是女孩。如果标签匹配，他们更有可能被复制过来；如果不匹配，他们被包含进去的可能性就较小。该模型还加入了一些全新的成员，以及一些已经在派对现场但并未出现在原始群体中的人。
研究人员发现，这种简单的“复制-粘贴-加点花样”机制创造了非常逼近真实的网络。当他们运行模拟时，他们发现该模型自然地产生了一种特定的数学模式，即关于每个人连接数量的幂律（power law）。这意味着在这些模拟世界中，少数人成为了超连接的“枢纽”，而大多数人只有很少的连接，就像现实中的社交网络一样。他们还绘制了“标签”（特征）如何随时间在网络中传播的图谱。他们发现，如果复制作用非常强（高同质性），群体往往会变得非常统一——就像一个满屋子人都穿着同一种颜色衬衫的房间。然而，即使复制作用很强，系统最终也会达到平衡，使得每个标签的总人数在长期内保持不变，即便单个群体看起来截然不同。
为了证明其模型的有效性，作者教会了计算机“学习”游戏的规则。他们使用了一种名为随机期望最大化（Stochastic Expectation Maximization, SEM）的技术。想象一下，你是一名侦探，试图仅通过观察人们玩游戏来推断游戏的规则。你先做一个猜测，观察几次动作，调整你的猜测，然后重复。作者展示了这种方法在他们用 CHILI 生成的伪数据上表现得非常好；计算机能够准确猜出他们用来创建数据的确切规则。随后，他们将这种“侦探工作”应用于现实世界的数据，例如美国参议员共同赞助的法案，或 Enron 公司员工发送的电子邮件。例如，在 Enron 数据上，该模型表明电子邮件群体的形成方式看起来是“异质性”的（异性相吸/异类相吸），作者解释说，这可能是因为电子邮件通常将一个核心群体连接到许多不同的局外人，而不是仅仅精确地复制之前的邮件链。
最后，团队尝试使用他们的模型来寻找“社区”——即属于彼此的人群。他们使用了一种名为模拟退火（simulated annealing）的方法，这就像计算机通过缓慢冷却金属来寻找其最强形态，但在这里，它被用于寻找标签的最佳排列。他们在现实数据集（如高中社交互动和参议院法案）上测试了该方法。结果喜忧参半，但非常令人期待。在一些其他标准方法（即假设群体是独立形成的）失效的棘手数据集上，CHILI 模型表现得更好。例如，在参议院法案数据上，它在识别政治党派方面优于其他方法。然而，作者承认这种方法非常缓慢且计算成本高昂，就像试图通过逐一检查每一个可能的移动来解决一个巨大的拼图。虽然它不是一个能瞬间解决所有问题的万能药，但本文表明，忽视“群体复制群体”这一事实可能是一个巨大的错误。通过显式地模拟边如何依赖于先前的边以及其中人的标签，我们或许能更清晰地描绘复杂的社会系统是如何生长和变化的。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。