导语


社团结构是复杂网络中最普遍也是最重要的拓扑特性之一，广义上的社团是具有共同兴趣爱好或者具有相似行为或相互关联的个体的集合，通常对应于复杂网络中内部连接紧密而外部连接稀疏的节点的集合。社团检测不仅对探究复杂网络的生成机制和潜在规律具有重要意义，同时在数学、物理学、生物学、计算机科学、社会科学等领域具有广泛的应用价值，研究社团检测算法有助于我们加深对复杂系统组织机制的理解。高阶网络读书会第十二期分享将由中山大学的吴洵洵和吴志颖分别从随机块模型和局部社团角度展开，共解读 7 篇相关文献，欢迎感兴趣的朋友预约参与直播。

本期分享将聚焦于高阶网络中的社团结构，围绕以下2个要点进行：

1. Hybrid-order Stochastic Block Model for Community Detection

2. 高阶网络的局部社团检测

高阶网络读书会由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，自2022年6月28日开始，每周四晚上19:30-21:30举办，持续时间预计 10-12周。期间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本季读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。欢迎对本话题感兴趣的朋友报名参加！详情见文末。






高阶网络中的社团检测-上




与读书会主题之间的关系


社团检测是复杂网络分析中经典的研究问题之一，其目的是将网络划分为内部连接紧密而外部连接稀疏的子结构。经典的社团检测方法大多只依赖于网络的低价结构，忽略了高阶连接模式，因此无法捕获复杂网络的构建块。因此融合网络的高阶结构，从生成模型的角度探索高阶结构、低阶结构与社团结构之间的内在关联，可以有效利用高阶信息，同时保持网络原始的拓扑特性，得到更为准确的社团检测结果，并提供了社团和网络形成机制的可能解释。


主讲人

吴洵洵，中山大学计算机学院在读博士生。主要研究兴趣为社团检测、随机块模型等。


分享题目：Hybrid-order Stochastic Block Model for Community Detection


分享简介

社团检测是复杂网络领域中的经典问题之一，其目的是将网络划分为内部连接紧密而外部连接稀疏的子结构，生成模型因其强有力的理论基础和可解释性得到了广泛的研究。模体是网络中出现的高阶连接模式，它对理解复杂网络的结构和潜在机制至关重要。经典的社团检测方法大多只依赖于网络的低阶结构，忽略了高阶连接模式，因此无法捕获复杂网络的构建块。如何有效利用模体结合生成模型进行更为精确的社团检测？


本次分享是论文解读。将围绕如下要点进行：
  1. 基于随机块模型的社团检测

  1. 基于高阶结构的社团检测


解读论文：

1. Karrer B, Newman M E J. Stochastic blockmodels and community structure in networks[J]. Physical review E, 2011, 83(1): 016107.
2. Benson AR, Gleich DF, Leskovec J. Higher-order organization of complex networks. Science. 2016 Jul 8;353(6295):163-6.
3. Li P Z, Huang L, Wang C D, et al. Edmot: An edge enhancement approach for motif-aware community detection . KDD 2019: 479-487
4. XunxunWu, Chang-Dong Wang, Pengfei Jiao: Hybrid-order Stochastic Block Model. AAAI 2021: 4470-4477.


分享大纲

  • 背景介绍

    • 社团检测

    • 生成模型

    • 概率图模型

  • 基于随机块模型的社团检测

    • 基本思想

    • 随机块模型（0-1edge）

    • 随机块模型（multiedge）

  • 基于高阶结构的社团检测

    • Higher-order organization of complex networks

    • EdMot

    • HSBM

  • 展望





    高阶网络中的社团检测-下




    与读书会主题之间的关系


    局部社团检测旨在搜索网络中给定种子节点附近的小区域以发现节点簇，为多种下游任务如图像分割、商品推荐提供了低成本的解决方案。早期的局部社团检测技术无法考虑网络中至关重要的高阶结构，由此衍生出基于高阶网络的局部社团检测技术，能够有效利用高阶信息，以扩展局部社团检测的应用范围。


    主讲人

    吴志颖，中山大学计算机学院2年级硕士研究生，主要研究方向为局部图挖掘、区块链去匿名化等。


    分享题目：高阶网络的局部社团检测


    分享简介：

    网络中的社团检测是一个活跃的研究领域。新算法的开发继续受到极大的关注，特别关注于提高准确性，并开发高效的计算方法，以应用于大型数据集。尽管现有社团检测方法已取得了进展，但不少方法都依赖于整个网络结构。而在不少应用中，研究者往往倾向于探索一个小区域内的社团，以避免分析整个网络所带来的计算负担。局部社团检测正是这样一种方法，它通过在指定的种子节点周围搜索，以极低成本构建出高质量的局部社团。针对经典方法无法感知网络中高阶结构的问题，本期分享将关注于高阶网络中的局部社团检测技术，为相关应用与实践提供指导。


    本期分享将聚焦于高阶网络中的局部社团检测，围绕如下要点进行：
    1. 简单图中的局部社团检测
    2. 基于网络模体的局部社团检测

    3. 超图中的局部社团检测


    分享大纲

    • 介绍高阶网络的局部社团检测技术

    • 背景知识

      • 局部社团发现的概念和相关应用场景

      • 如何描述局部社团检测

      • 传统局部社团检测技术及其框架

    • 网络模体&局部社团

      • 网络模体与模体计数

      • 基于网络模体的局部社团发现

      • 相关实验

    • 超图&局部社团

      • 超图简介与超图规约

      • 超图局部社团检测

      • 相关实验

    • 参考文献


    本次分享相关文章：

    本次分享是论文精读。首先介绍简单图中的局部社团检测，接着以高阶网络结构的视角，讨论局部社团检测技术如何扩展到高阶网络中，最终结合相关实验和应用说明方法的有效性。主要讲解的文章如下：

    • 精读的文章：

    • Andersen R, Chung F, Lang K. Local graph partitioning using pagerank vectors[C]//2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). IEEE, 2006: 475-486.

    • Yin H, Benson A R, Leskovec J, et al. Local higher-order graph clustering[C]//Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017: 555-564.

    • Liu M, Veldt N, Song H, et al. Strongly local hypergraph diffusions for clustering and semi-supervised learning[C]//Proceedings of the Web Conference 2021. 2021: 2092-2103.

    • 理论与应用方向的论文：

    • Benson A R, Gleich D F, Leskovec J. Higher-order organization of complex networks[J]. Science, 2016, 353(6295): 163-166.

    • Liu M, Gleich D F. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering[J]. Advances in neural information processing systems, 2020, 33: 5023-5035.

    • Klicpera J , Bojchevski A , S Günnemann. Predict then Propagate: Graph Neural Networks meet Personalized PageRank[J]. 2018.

    • Veldt N, Benson A R, Kleinberg J. Hypergraph cuts with general splitting functions[J]. SIAM Review, 2022, 64(3): 650-685.


    本期主持人

    高爽， 厦门大学在读博士生，主要研究方向基于脑数据的高阶网络分析。


    本期涉及的知识概念

    社团结构 Community Structure

    社团检测 Community Detection

    模体 motif

    生成模型 Generative Model

    随机块模型 Stochastic Block Model

    贝叶斯网络 Bayesian Networks

    概率图模型 Probabilistic Graphical Model (PGM)

    局部社团检测 local community discovery

    电导率 Conductance

    网络模体 Network motif

    超图 Hypergraph


    当前，已经收录在集智百科词条的相关知识有：

    1. 社团结构：https://wiki.swarma.org/index.php/%E7%A4%BE%E5%9B%A2%E7%BB%93%E6%9E%84

    2. 模块度：https://wiki.swarma.org/index.php/%E6%A8%A1%E5%9D%97%E5%BA%A6

    3. 层次聚类：https://wiki.swarma.org/index.php/%E5%B1%82%E6%AC%A1%E8%81%9A%E7%B1%BB_Hierarchical_clustering

    4. 概率图模型：https://wiki.swarma.org/index.php/%E6%A6%82%E7%8E%87%E5%9B%BE%E6%A8%A1%E5%9E%8B

    5. 贝叶斯网络：https://wiki.swarma.org/index.php/%E8%B4%9D%E5%8F%B6%E6%96%AF%E7%BD%91%E7%BB%9C

    6. 网络模体：https://wiki.swarma.org/index.php/%E7%BD%91%E7%BB%9C%E6%A8%A1%E4%BD%93_Network_motifs

    7. 超图：https://wiki.swarma.org/index.php/%E8%B6%85%E5%9B%BE_Hypergraph

    8. 复杂系统：https://wiki.swarma.org/index.php/%E5%A4%8D%E6%9D%82%E7%B3%BB%E7%BB%9F_Complex_Systems





    直播信息




    时间：
    2022年10月13日（周四）晚上19:30-21:30

    参与方式：

    • 集智俱乐部 B 站免费直播，扫码可预约：
    扫码报名
    • 文末扫码付费参加高阶网络读书会可加入腾讯会议，可提问交流，加入群聊，获取回看地址及更多学习资料，成为集智网络科学社团种子用户，与网络科学社团的一线科研工作者沟通交流，共同推动网络科学社团的发展



    高阶网络读书会招募中


    随着对现实世界探索的不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了高阶网络读书会。


    高阶网络读书会由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，第一期分享从 6月 28日（周二）20:00 开始，后续每周分享时间为每周四 19:30-21:30 进行，预计持续 10-12 周。这期间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。欢迎感兴趣的朋友参与。



    本季读书会详情与报名方式请参考：
    探索复杂系统高阶交互的奥秘 | 高阶网络读书会启动


    点击“阅读原文”，报名直播