Generative hypergraph clustering: From blockmodels to modularity
Generative hypergraph clustering: From blockmodels to modularity
复制标题
DOI：
10.1126/sciadv.abh1303
复制
发表时间：
2021-07-01
期刊：
影响因子：
13.6
通讯作者：
Benson, Austin R.
中科院分区：
文献类型：
--
作者：
Chodrow, Philip S.;Veldt, Nate;Benson, Austin R.
超图是一种自然的建模范式，网络系统与多路交互。网络分析中的一项标准任务是识别密切相关或紧密互连的节点。提出了一个节点度和边大小不均匀的聚类超图的概率生成模型。近似最大似然推断在这个模型中导致聚类目标，概括了流行的模块化目标的图。由此，我们推导出一个推理算法，概括了鲁汶图社区检测方法，和一个更快的，专门的变种，其中边缘预计完全位于集群内。使用合成和经验数据，我们证明了专门的方法是高度可扩展的，可以检测集群基于图形的方法失败。我们还使用我们的模型来寻找可解释的高阶结构，在学校的联系网络，美国国会法案共同赞助和委员会，产品类别的copurchasing行为，酒店位置从网页浏览会话。
Hypergraphs are a natural modeling paradigm for networked systems with multiway interactions. A standard task in network analysis is the identification of closely related or densely interconnected nodes. We propose a probabilistic generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum likelihood inference in this model leads to a clustering objective that generalizes the popular modularity objective for graphs. From this, we derive an inference algorithm that generalizes the Louvain graph community detection method, and a faster, specialized variant in which edges are expected to lie fully within clusters. Using synthetic and empirical data, we demonstrate that the specialized method is highly scalable and can detect clusters where graph-based methods fail. We also use our model to find interpretable higher-order structure in school contact networks, U.S. congressional bill cosponsorship and committees, product categories in copurchasing behavior, and hotel locations from web browsing sessions.