1203论文速读

1、Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks∗ （多层网络社区检测的层次随机块模型 ）

全文总结：本文提出了一种新颖的贝叶斯模型，称为分层随机块模型（HSBM），用于检测多层网络中的社区。多层网络由同一组节点之间的多种类型的边或关系组成。HSBM的关键特点是它能够对不同网络层建模不同的社区结构，同时还能捕捉层之间的潜在依赖关系。这与许多现有模型假设所有层具有相同社区结构的做法形成对比。HSBM使用分层狄利克雷先验来建模跨层的社区标签，从而实现每层社区数量的自动和自适应选择。作者开发了一种高效的切片采样算法来进行模型的后验推断。在模拟和真实数据上的实证结果表明，HSBM相比单层替代方案具有更出色的性能，特别是在揭示真实世界多层网络中的有趣结构方面。

1. 文章研究背景和要解决的问题挑战

• 多层网络(multiplex network)已经在许多领域广泛应用,成为建模复杂现实网络的强大工具。

• 现有的许多社区检测模型都假设不同网络层具有相同的社区结构,这种假设过于局限,往往与现实情况不符。

• 需要开发能够考虑不同网络层之间潜在依赖关系的推断模型,特别是在社区检测任务中。

• 确定每个网络层的社区数量是社区检测的一个挑战,在多层网络中尤其如此,因为不同层可能具有不同的社区结构。

  本文旨在提出一种新的贝叶斯模型,能够在多层网络中建模不同层之间可能存在的社区结构差异,同时自动确定每层的社区数量,以解决现有方法的局限性。

2. 具体实现

本文提出了一种新的层次随机块模型（HSBM），用于多层网络中的社区检测。该模型采用分层狄利克雷先验来建模不同网络层之间的依赖关系，并允许每个网络层具有不同的社区结构。具体来说，HSBM包括两个部分：层次标签分布和单层随机块模型。

在层次标签分布中，我们假设社区标签的概率分布服从一个层次狄利克雷过程（HDP）。这使得我们可以灵活地建模社区结构，并且可以自动选择每个网络层所需的社区数量。在实际应用中，通过从HDP中采样得到的社区标签来描述网络的不同层次结构。

在单层随机块模型中，对于每个网络层，我们假设其链接概率符合随机块模型（SBM）的形式。具体的，每个节点被分配到某个社区，而社区内部的节点之间存在较高的连接概率，而不同社区之间的节点则具有较低的连接概率。为了更好地捕捉不同社区之间的相互作用，我们在SBM中引入了跨社区链接权重。

为了高效地推断HSBM的参数，本文开发了一个基于片切技术的高效抽样算法。该算法可以在不计算复杂后验概率的情况下，直接对HSBM的参数进行抽样。通过实验验证，本文提出的HSBM方法比传统的单层随机块模型在多层网络中的性能更好，并能够发现更有趣的网络结构。

关键公式步骤如下：

1. 引入辅助变量$u$和$v$,构建联合密度函数$p(A,\eta ,g,k,\gamma \prime ,\pi \prime ,u,v)$,并采用块吉布斯采样的方式对该联合密度进行推断。

2. 对于变量$(u,{\gamma }^{\prime })$和$(v,{\pi }^{\prime })$,分别采用切片采样的方法进行采样,其中$\gamma \prime$和$\pi \prime$的后验分布分别服从Beta分布。

3. 对于潜在社区分配$g$，采用基于条件概率的采样方法,其中条件概率$\rho ti(g)$的计算涉及到网络连接概率$\eta$和社区分配$z$。

4. 对于社区分配$k$,也采用基于条件概率的采样方法,其中条件概率的计算涉及到网络连接概率$\eta$和社区分配$g$。
   本文提出的方法能够在多层网络中建模不同层之间可能存在的社区结构差异,并自动确定每层的社区数量,从而克服了现有方法的局限性。

与传统的单一层次的社区检测算法相比，HSBM可以更好地处理跨时间点的社区结构变化。此外，本文还比较了HSBM与其他几种常见的社区检测算法的性能，包括单层DP-SBM、SC-sliced、SC-avg、SC-ba、SC-omni和PisCES等。这些算法包括单独应用于每个时间点的DP-SBM、利用平均邻接矩阵的SC-avg、利用谱聚类的SC-sliced、SC-ba和SC-omni以及利用PisCES优化的谱投影矩阵平滑算法。
本文提出的HSBM可以有效地处理跨时间点的社区结构变化问题，从而为研究者提供了一种更准确地识别网络中社区结构的方法。同时，本文还比较了HSBM与其他几种常见的社区检测算法的性能，为选择合适的算法提供了参考。

3. 实验设计

本文主要介绍了对多层网络的社区结构进行建模和分析的方法，并通过实验证明了该方法的有效性。具体来说，本文使用了隐含层次块模型（HSBM）来对多层网络进行建模，并使用归一化互信息（NMI）作为性能评估指标。在实验中，作者将HSBM与其他几种常见的多层网络建模方法进行了比较，包括谱聚类（SC）、谱切片（SC-sliced）和全向度量（PiCES）。结果表明，HSBM在各种情况下都表现出了优异的性能，尤其是在具有不同社区结构的多层网络中。此外，作者还使用FAO贸易网络数据集进行了实际应用，结果显示HSBM能够有效地识别出不同的贸易模式并将其分配给不同的社区。总之，本文提出了一种有效的多层网络社区结构建模方法，并证明了其在实际应用中的有效性。

4. 总结

值得精读
该论文提出了一种新的贝叶斯模型——HSBM（Hierarchical Stochastic Block Model），用于社区检测在多层网络中的应用。相比于传统的模型，HSBM能够更好地处理不同层之间的依赖关系，并且可以自动选择合适的社区数量。此外，该论文还提出了一种基于slice sampler的高效采样算法，使得模型的推断更加准确和快速。
该论文的主要贡献在于提出了HSBM这一新的贝叶斯模型，以及相应的高效采样算法。HSBM不仅考虑了节点在不同层之间的联系，还可以自动选择合适的社区数量，从而更好地捕捉到网络结构的特点。同时，该论文提出的slice sampler算法也具有一定的创新性，能够在保证准确性的同时提高采样的效率。

5. 局限性

虽然该论文提出的方法已经取得了很好的效果，但是在实际应用中仍然存在一些挑战。例如，在大规模网络上的计算开销较大，需要进一步优化算法以提高效率；另外，对于不同的网络类型和数据分布，可能需要针对具体情况进行参数调整和模型改进。因此，未来的研究方向包括但不限于：1）探索如何进一步优化采样算法以提高效率；2）研究如何根据具体的网络类型和数据分布来调整模型参数；3）将HSBM与其他算法相结合，构建更加强大的社区检测工具。

2、Robust Overlapping Community Detection in Complex Networks With Graph Convolutional Networks and Fuzzy C-Means（基于图卷积网络和模糊C均值的复杂网络中强重叠社区检测 ）

全文总结：本文提出了一种称为GCNFCM的新方法，用于检测复杂网络中的重叠社区。GCNFCM利用图卷积网络（GCNs）和模糊C均值（FCM）来实现节点的强大特征学习，并识别最优的重叠社区结构。关键创新包括用于捕获网络拓扑和节点属性的双解码器图自编码器，以及将FCM与模块度Q算法相结合，以指导重叠社区检测过程，而无需事先了解社区数量。在真实世界复杂网络上的实验结果表明，GCNFCM在产生凝聚力强的社区和识别真实社区方面优于最先进的重叠社区检测方法。

1. 文章研究背景和要解决的问题挑战

• 复杂网络中存在着自然重叠的社区结构,即一个节点可以属于多个社区。这种重叠社区结构对于社交影响检测、网络攻击检测和推荐系统等应用非常重要。

• 现有的社区检测方法往往难以同时捕捉网络拓扑和节点属性特征,导致重叠社区检测效果不佳。

• 需要一种新的方法来实现对节点特征的鲁棒学习,并识别出最优的重叠社区结构,而不需要事先知道社区数量。

2. 具体实现

本文提出了一种名为GCNFCM的方法，用于在复杂网络中检测重叠社区。该方法结合了图卷积网络（Graph Convolutional Networks, GCNs）和模糊C均值（Fuzzy C-Means, FCM）算法，以及模块化Q算法来识别重叠社区。。

（1）. 问题定义和符号说明

• 复杂网络（Complex Network, CN）：定义为图 $G(V,E)$，其中 $V$ 表示节点集合，$E$ 表示边集合，即节点之间的关系。
• 邻接矩阵（Adjacency Matrix） $A$：表示网络中节点间的关系，若节点 $vi$ 和 $vj$ 之间有边则 $a_{ij}=1$，否则 $a_{ij}=0$。
• 社区隶属矩阵（Community Affiliation Matrix） $H$：表示节点与社区的关系，$h_{vk}$ 表示节点 $v$ 属于社区 $k$ 的程度。

（2）. 节点特征提取和学习

GCN-Encoder

GCN-Encoder用于从网络中学习节点的嵌入表示。关键步骤如下：

• 预处理：计算邻接矩阵 $A$ 的规范化拉普拉斯矩阵 $L$。
  $$L=I_n-D^{-1/2}A{D}^{-1/2}$$
  其中 $I_n$ 是单位矩阵，$D$ 是度矩阵。

• 图卷积层：使用图卷积层处理节点特征，得到低维潜在表示 $Z$。
  $$H^{(l+1)}=\sigma \left({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)}\right)$$
  其中 $\sigma$ 是激活函数，$W^{(l)}$ 是可训练的权重矩阵。

双解码器（Dual-Decoder）

• 内积解码器（Inner Product Decoder, IPD）：重建邻接矩阵 $\hat{A}$。
  $$\hat{A}=\sigma (Z{Z}^T)$$

• 图卷积解码器（Graph Convolutional Decoder, GCD）：重建节点特征矩阵 $\hat{X}$。
  $$\hat{X}=f(Z,A)=\tilde{A}\text{ReLU}(\tilde{A}Z{W}^{(0)})W^{(1)}$$

（3）. 重叠社区检测

FCMQ算法

结合FCM和模块化Q算法进行重叠社区检测。

• FCM算法：通过迭代优化目标函数进行社区划分。
  $$J_m=\sum _{i=1}^n\sum _{j=1}^C{U}_{ij}^m\Vert Z_i-C_j{\Vert }^2$$
  其中 $U_{ij}$ 是节点 $i$ 在社区 $j$ 中的隶属度，$m$ 是模糊因子。

• 模块化Q计算：评估社区结构的质量。
  $$\tilde{Q}=\sum _{k=1}^c\left(\frac{A(V_k,V_k)}{A(V,V)}-{\left(\frac{A(V_k,V)}{A(V,V)}\right)}^2\right)$$
  其中 $V_k$ 是社区 $k$ 中的节点集合。

3. 实验设计

本文主要介绍了GCNFCM算法在重叠社区检测方面的实验和结果分析。实验部分包括了实验设置、参数选择和评价指标等方面的内容。

首先，文章选择了十个真实数据集来评估GCNFCM算法的效果，这些数据集涵盖了不同规模、来源和内容的社区网络，并分为两类：只包含网络拓扑结构的数据集和包含节点属性的数据集。对于前者，使用公式（1）生成X矩阵；而对于后者，则利用TF-IDF算法计算每个文档的特征向量。

其次，在参数选择方面，作者采用了迭代实验的方法，对GCNFCM算法中的各个参数进行了优化。具体来说，作者使用了不同的层数和神经元数量来训练GCN自动编码器，并设置了学习率、迭代次数等参数。最终，作者得到了一组最优的参数组合，以确保GCNFCM算法能够得到最佳效果。

最后，在评价指标方面，作者选择了三种常用的社区检测指标：重叠归一化互信息（ONMI）、欧米茄指数Q-Index（OMG）和模块度测量（Q）。其中，ONMI是一种广泛用于评估社区检测算法的指标，它基于信息论准则比较识别出的社区与真实社区之间的相似性。OMG是另一种评估社区检测算法的指标，它是调整兰德指数的重叠版本，适用于处理节点可能同时属于多个社区的情况。而Q则是用来评估社区检测质量的一种指标，它可以保证社区内部关系更紧密，社区之间连接更稀疏。

总的来说，通过实验和结果分析，本文证明了GCNFCM算法在重叠社区检测方面的有效性，并提供了详细的实验设置、参数选择和评价指标等方面的说明。

4. 总结

值得精读

• 论文提出了一种新的社区检测方法GCNFCM，能够有效地识别网络中的重叠社区结构。

• GCNFCM利用了图卷积神经网络（GCN）和模糊C均值聚类（FCM）的优点，并结合了质量指数Q来优化结果。

• 论文使用了多个真实世界的数据集进行了实验验证，证明了GCNFCM在各种规模和类型的网络中都能表现出色。

• GCNFCM通过将GCN应用于节点嵌入的提取以及FCM用于社区检测的方法相结合，实现了准确地识别重叠社区结构。

• GCNFCM使用了双解码器架构，考虑了节点拓扑和属性信息，从而提高了节点嵌入的质量。

• 该方法不需要预先知道社区的数量，而是利用了Q算法来消除这个限制。

5. 局限性

GCNFCM仍然存在可扩展性和超参数选择敏感度等问题，需要进一步研究解决。
可以探索并行处理技术来提高效率，实现更大规模的网络数据处理。
对于超参数的选择问题，可以考虑自动调参技术来提高通用性和用户友好性。
进一步增强解释性，揭示社区检测背后的原理，有助于更好地理解和应用GCNFCM。

3、Event detection from real-time twitter streaming data using community detection algorithm（使用社区检测算法从实时推特流数据中检测事件 ）

全文总结：本文提出了一种更快的基于位置的事件检测方法，从实时推特数据流中检测事件而不影响准确性。该方法包括四个关键步骤：1）一种新的动态加权方案称为条件词频-平均逆窗口频率（CTF-AIWF），用于捕捉新兴关键词；2）一种新的聚类算法称为边缘显著性基于Louvain算法（ESBLA），用于有效地将同一事件的关键词分组；3）一种新的基于内容的位置检测技术，用于处理微博数据中的非正式语言；4）在谷歌地图上可视化检测到的事件。该方法旨在自动化从无休止的推文流中检测事件的过程，以便尽可能早地识别重要事件。

1. 文章研究背景和要解决的问题挑战

（1）. 社交媒体服务的日益普及导致了大量含噪声的推特数据在互联网上传播。从这无休止的推特流中手动提取有价值的事件信息是一个巨大的挑战。因此需要自动化事件检测的过程,以便尽快识别重要事件。

（2）. 大多数现有方法更关注"发生了什么",但要定义一个事件,还需要回答"何时"和"何地"。对于紧急事件,位置和时间参数非常重要。

（3）. 现有方法存在一些局限性,如同一事件关键词被分到多个簇、执行时间过长、无法识别事件位置等。

2. 具体实现

本文提出了一种从实时Twitter流数据中检测事件的方法，该方法包括四个主要步骤：提取事件候选关键词、事件聚类识别、事件地点检测和事件在谷歌地图上的可视化。下面结合关键公式详细说明本文的方法论：

1. 提取事件候选关键词

本文提出了一种基于TF-IDF的新的动态加权方案，称为条件词频-平均逆窗口频率（CTF-AIWF），用于从数据的时间动态中捕获新兴关键词。

• CTF（Conditional Term Frequency）：计算当前时间窗口中关键词k的频率。
  $$CTFk=\frac{Nk}{N}$$
  其中，$N$ 代表当前时间窗口中的总推文数，$Nk$ 代表包含关键词k的推文数。

• AIWF（Average Inverse Window Frequency）：计算前p个时间窗口中关键词k的平均逆窗口频率。
  $$AIWFk=\frac{{\sum }_{i=1}^p\log \frac{Ni}{Nik}}{p}$$
  其中，$Ni$ 代表第i个时间窗口的总推文数，$Nik$ 代表第i个时间窗口中包含关键词k的推文数。

• ECS（Event Candidate Score）：计算关键词k的事件候选分数，即CTF和AIWF的乘积。
  $$ECSk=CTFk\times AIWFk$$

• ECS的哈希标签增强：对于哈希标签，通过乘以一个增强因子（本文中取值为2）来提高其ECS值。
  $$ECSh=\text{hashtag\_booster}\times ECSk$$

2. 事件聚类识别

提出了一种基于边重要性的Louvain算法（ESBLA），通过改进的Louvain社区检测算法对事件候选关键词进行聚类。

• 图构建：构建一个无向图，节点代表事件候选关键词，如果两个关键词在同一条推文中共现且其中一个是新兴关键词，则在两个节点之间画一条边。每条边的权重是两个节点之间语义和拓扑结构相似性的总和。

• 语义相似性权重（TCW-AINCW）：通过Jaccard系数和逆邻接节点相关权重的平均值来计算。
  $$TCW(ki,kj)=\frac{T{F}_{ki\cap kj}}{T{F}_{ki\cup kj}}$$
  $$AINCW(ki,kj)=\frac{{\sum }_{km\in \text{neigh}(ki)}\log \frac{T{F}_{ki\cup km}}{T{F}_{ki\cap km}}+{\sum }_{kn\in \text{neigh}(kj)}\log \frac{T{F}_{kj\cup kn}}{T{F}_{kj\cap kn}}}{N_{eigh}(ki)+N_{eigh}(kj)}$$
  $$semweight(ki,kj)=TCW(ki,kj)\times AINCW(ki,kj)$$

• 结构权重：通过Jaccard相似性计算。
  $$structweight(ki,kj)=\frac{N_{eigh}(ki)\cap N_{eigh}(kj)}{N_{eigh}(ki)\cup N_{eigh}(kj)}$$

• 边的总权重：
  $$w(ki,kj)=semweight(ki,kj)+structweight(ki,kj)$$

3. 事件地点检测

使用基于内容的空间分析技术来检测事件的位置，通过提取每个事件社区中的位置关键词，并使用国家-州-城市数据库来标记这些关键词。

4. 事件在谷歌地图上的可视化

通过Jaccard相似性提取每个事件社区的代表性推文，并在谷歌地图上进行可视化，以蓝色标记表示事件发生地点，并展示相关推文。

本文的方法论通过结合时间窗口分析、加权图社区检测算法和基于内容的位置检测技术，实现了从Twitter流数据中实时检测事件的目标，并在谷歌地图上进行了有效的可视化展示。

该论文提出了两种方法来检测事件：基于监督学习的分类模型和无监督聚类算法。在监督学习中，使用了机器学习和深度学习分类方法，如卷积神经网络和支持向量机等，来预测文本的情感和主题，并将结果与视觉特征相结合以识别特定类型的事件。在无监督聚类中，采用了基于图论的社区检测算法，如Louvain算法，以及基于时间窗口的图形聚类方法，用于处理实时流数据并发现潜在的事件群集。

该论文提出的无监督聚类算法通过引入边缘重要性权重和增强词法相似性计算，进一步提高了事件检测的准确性和效率。同时，还考虑了社交媒体中的特殊词汇，如话题标签（hashtags），并将其纳入到关键词提取和聚类过程中，以更好地捕捉事件的主题和语义信息。

3. 实验设计

本文进行了三个实验来比较和评估提出的事件检测方法的质量和运行时间性能。首先，使用了基于关键词图的KeyGraph方法和基于过滤和层次聚类的方法作为基准方法来进行比较。其次，通过手动搜索Google上的新闻来验证每个方法检测到的事件是否真实存在。最后，对这三个方法在Precision、Recall和F-Measure等指标上进行了评估，并得出了实验结果。

第一个实验是比较提出的事件检测方法与两个基准方法之间的质量差异。实验中使用的数据集是由Twitter Streaming API收集的印度用户在2018年8月和9月期间发布的11万条推文。实验结果表明，提出的事件检测方法在召回率方面显著优于其他两种方法，并且在精度方面几乎等于其他方法的表现。

第二个实验是通过手动搜索Google上的新闻来验证每个方法检测到的事件是否真实存在。由于没有可用的真实世界数据集，因此这种方法是不现实的。但是，通过对Google上已知事件的搜索，可以验证所提出的方法检测到的事件是否真实存在。

第三个实验是对这三个方法在Precision、Recall和F-Measure等指标上进行评估，并得出实验结果。实验结果表明，提出的事件检测方法在召回率方面表现最好，在精度方面也接近于其他方法的表现。此外，提出的事件检测方法的运行时间比其他两种方法都要短。

综上所述，本文通过三个实验比较和评估了提出的事件检测方法的质量和运行时间性能，并得出了实验结果。这些结果表明，提出的事件检测方法具有较高的质量和较短的运行时间，是一种有效的事件检测方法。

4. 总结

值得精读

• 该研究提出了一种新的事件检测方法，能够及时地从Twitter中检测出具有位置信息的新兴事件。
• 该方法采用了时间窗口分析来处理流式数据，并使用了 Louvain 算法来快速地将事件聚类。
• 该方法还提出了一个新的基于内容的地点检测技术，可以更准确地识别事件发生的地点。
  实验结果表明，该方法在质量和运行时间方面都优于其他两种基准方法。

5. 局限性

可以进一步改进该方法，使其更加适用于不同类型的事件。
可以考虑使用深度学习等技术来提高事件检测的质量和准确性。
可以探索如何利用社交媒体上的用户行为数据来预测未来的事件发生。

4、Online estimation and community detection of network point processes for event streams（事件流中网络点过程的在线估计和社区检测 ）

全文总结：这篇论文探讨了如何使用点过程模型对网络中的事件流进行实时估计和社区检测。传统的网络建模方法通常忽略了事件流的时间动态性，而该论文提出的点过程模型则能够更好地捕捉这种动态性。然而，由于计算复杂度的问题，现有的点过程模型在处理大规模稀疏网络时存在瓶颈。为了解决这个问题，作者提出了一种快速在线变分推断算法，用于估计网络中事件流的潜在结构，并描述了如何将这种算法应用于网络模型以识别社区结构。实验结果表明，在处理大型稀疏网络时，该算法具有较高的效率和准确性。此外，该框架还可以轻松地扩展到其他流行的网络结构上。

1. 文章研究背景和要解决的问题挑战

这篇文章的研究背景是网络模型中的社区结构发现。在现实世界中，许多网络都具有动态的时间成分，但传统的网络模型忽略了这个时间因素，只关注节点之间的连接关系。因此，为了更好地理解网络的动态行为，研究人员开始探索使用点过程作为网络模型的基础来实现社区结构的发现。然而，现有的方法存在计算复杂度高的问题，难以处理大规模稀疏网络。该文章提出了一种快速的在线变分推断算法，用于估计网络上动态事件到达的潜在结构，并通过实验验证了该算法的有效性。

2. 具体实现

该论文提出了一种在线学习框架来处理网络点过程数据，并利用这些数据估计网络社区结构。他们使用了基于隐变量模型的变分推断方法，通过更新累积历史信息来实现连续实时地更新参数估计。具体来说，他们将时间窗口划分为多个时间段，每个时间段内都有一组事件发生。在每个时间段结束时，他们会根据当前的事件流重新计算节点之间的关系，并更新模型参数。此外，他们还提供了一些理论保证，证明他们的算法能够收敛到真实模型参数并具有良好的本地收敛率。

与传统的离线方法相比，该方法的优点在于可以快速适应新的数据流，并且可以在不需要重新训练整个模型的情况下进行增量式更新。此外，由于他们的方法是基于隐变量模型的变分推断方法，因此可以有效地避免维度灾难问题，并且能够在大型网络上运行。

本文提出的方法论是基于连续时间点过程的潜在网络模型，用于在线估计和社区检测。核心思想是利用网络中的事件流数据来动态更新社区结构。以下是文章中提到的关键公式和方法论的详细说明：

1. 点过程和条件强度函数：

   • 点过程是用于建模事件流的数学工具。在网络中，每个节点对之间的互动可以被视为一个点过程，其条件强度函数 ${\lambda }_{ij}(t)$ 描述了在时间 $t$ 发生互动的可能性。
   • 条件强度函数定义为：
     $$\lambda (t)=\underset{dt\to 0}{\lim }\frac{E(N[t,t+dt)|H(t))}{dt}$$
     其中 $N[t,t+dt)$ 表示在时间 $t$ 和 $t+dt$ 之间发生的事件数量，$H(t)$ 是历史信息滤波。

2. 网络点过程模型：

   • 文章提出了基于点过程的网络模型，其中节点之间的互动强度 ${\lambda }_{ij}(t)$ 依赖于节点的潜在社区归属。如果节点 $i$ 属于潜在类别 $z_i$，节点 $j$ 属于 $z_j$，则：
     $${\lambda }_{ij}(t)={\lambda }_{z_i{z}_j}(t)$$
   • 这种模型结构允许社区检测能够捕捉节点间互动的时间动态。

3. 在线变分推断算法：

   • 文章提出了一个在线变分推断框架，用于动态更新网络中的社区结构。该算法通过递归更新模型参数和节点的潜在成员身份，具有低内存成本。
   • 算法的关键更新步骤包括：
     • 更新潜在分布 $q^{(m)}(z)$：
       $$q^{(m)}(z_i)\propto {\pi }^{(m-1)}\exp \left({\mathbb{E}}^{q^{(m-1)}}(z_{-i}){\lambda }_m({\theta }^{(m-1)}|z)\right)\cdot S^{(m-1)}(z_i)$$
     • 更新点过程参数 $\lambda$：
       $${\lambda }^{(m)}={\lambda }^{(m-1)}+{\eta }_m\frac{\partial {\mathbb{E}}^{q^{(m)}}(z){\lambda }_m(\theta |z)}{\partial \lambda }$$
     • 更新社区比例 $\pi$：
       $${\pi }_k=\frac{1}{n}\sum _{i=1}^n{\tau }_{ik},\text{for }k=1,\dots ,K$$
   • 这里，$S(m)(z)$ 存储了每个个体 $i$ 和潜在类别 $k$ 直到当前时间窗口的累积群体证据。${\eta }_m$ 是自适应学习速度，可能依赖于 $m$。

4. 理论性质：

   • 文章还提供了关于所提出的在线变分算法的理论结果，包括在线估计器的遗憾界限和参数恢复的收敛速率。

3. 实验设计

本文主要介绍了在模拟数据和真实数据上的实验结果，以验证在线社区检测算法的性能，并与其他方法进行了比较。具体来说，作者进行了以下对比实验：

模拟数据实验：该实验使用了合成数据来测试算法的性能。作者考虑了不同网络大小、密度和参数设置的情况，并通过计算调整后的 Rand 系数（ARI）来衡量算法的社区恢复能力。结果显示，在小网络中初始化对算法的性能有很大影响，但在大网络中，算法能够很好地捕捉到真实的社区结构。

实验室数据实验：该实验使用了三个实验室数据集来测试算法的性能。作者将事件分为训练和测试期，并尝试预测测试期内两个节点之间的交互次数。作者还比较了在线算法和批量算法的预测效果，并发现在线算法能够在较短的时间内获得与批量算法相似的结果。

总的来说，这些实验表明了在线社区检测算法在处理大规模时间序列数据时具有很好的性能，并且可以应用于实际问题中的链接预测任务。

4. 总结

值得精读 互动强度

该论文提出了一种在线学习算法，用于估计大型网络结构中的社区结构，并使用动态模型来考虑社区结构的变化。该算法具有可扩展性和高效性，能够处理大规模数据集，并且在实验中表现出良好的性能。该论文的方法创新点在于提出了一个在线框架，可以快速地估计网络模型并更新参数，而不需要重新计算整个模型。此外，该论文还考虑了如何初始化算法以更好地适应不同的数据集，并提供了一些理论结果，如收敛性和社区恢复率等。

5. 局限性

未来的研究方向包括将该算法应用于更广泛的网络类型，例如社交网络和计算机网络等；探索如何处理网络中的异常事件和噪声；以及进一步研究如何利用其他类型的观测数据来提高算法的性能。

5、A new algorithm for communities detection in social networks with node attributes （具有节点属性的社会网络社区检测的新算法 ）

全文总结：

1. 文章研究背景和要解决的问题挑战

这篇论文介绍了一种新的算法——Fast-Bi Community Detection（FBCD），用于在带有节点属性的社会网络中检测社区结构。社会网络可以表示为一个二分图，由两个节点集合和连接这些节点的边组成。具有相似节点属性的人们往往倾向于形成隐藏的社区或群组。虽然有许多社区检测算法已经被应用于文献中的各种领域，但该方法仍然存在一些缺点。因此，作者提出了FBCD算法，旨在高效地检测社交网络中的社区结构。该算法的主要思想是探索二分图中的最大匹配，以降低算法的复杂度。实验结果表明，与先前的文献相比，所得到的社区质量更高。关键词包括社会网络、最大匹配、节点属性、二分图、社区检测等。

FBCD算法解决了传统社区检测算法的一些问题，例如需要处理所有存在的边、无法适应不同的社区定义和用户需求等。它还提供了一种可靠的方法来评估社区的质量，从而更好地理解网络中的社区结构。

2. 具体实现

本文提出了一种新的方法，用于在具有节点属性的社交网络中检测社区结构。这种方法被称为快速双社区检测（Fast-Bi Community Detection, FBCD）。FBCD方法的核心思想是利用二分图中的最大匹配来降低算法的复杂度，并提高社区检测的效率。下面是本文中提到的一些关键概念和公式，以及它们如何被用于FBCD方法中：

1. 二分图（Bipartite Graph）：

   • 定义：一个简单的图，其顶点集可以被划分为两个不相交的子集，图中的每条边连接这两个子集中的一个顶点。
   • 应用：社交网络中的节点（人）和节点属性（如兴趣、行为等）可以用二分图表示，其中一边的节点代表人，另一边的节点代表属性。

2. 最大匹配（Maximum Matching）：

   • 定义：在二分图中选择一组边，使得没有两条边共享一个公共顶点，且这组边的数量最大。
   • 应用：FBCD方法利用最大匹配来减少需要考虑的边的数量，因为最大匹配的边是互不相交的，这有助于算法的分布式处理和降低搜索空间。

3. 社区（Community）：

   • 定义：一个社区是图中的一个子集，其中内部节点之间的连接比与外部节点的连接更为密集。
   • 应用：FBCD方法旨在通过最大匹配找到这样的社区结构。

4. 伪社区（Pseudo-Community）：

   • 定义：与特定节点对（u, v）相关的子二分图，包含所有与u相连的节点和所有与v相连的节点。
   • 应用：FBCD方法通过计算伪社区的密度来评估社区的紧密程度。

5. 质量度量（Quality Metrics）：

   • 稳定性（Stability）：
     • 公式： σ ( ⟨ A , B ⟩ ) = ∣ { X ⊆ A ∣ ϕ ( X ) = B } ∣ 2 ∣ A ∣ \sigma(\langle A, B \rangle) = \frac{|\{X \subseteq A | \phi(X) = B\}|}{2^{|A|}} σ(⟨A,B⟩)=2∣A∣∣{X⊆A∣ϕ(X)=B}∣​
     • 应用：衡量社区B对节点集A的依赖程度，稳定性越高，社区质量越好。
   • 模块性（Modularity）：
     • 公式：$Q=\frac{1}{2m}{\sum }_{i,j}[A_{ij}-\frac{K_i\cdot K_j}{2m}]\delta (c_i,c_j)$
     • 应用：衡量网络划分的质量，高模块性表示社区内部连接密集，而社区间连接稀疏。
   • 键（Bond）：
     • 公式：$\text{Bond}(⟨A,B⟩)=\frac{\text{Supp}(\wedge A)}{\text{Supp}(\vee A)}$
     • 应用：衡量社区的连接紧密度，键值越高，社区质量越好。
   • 重叠度（Overlapping）：
     • 公式：$\text{Overlapping}=\frac{|E_{inc}|-\frac{(2|E_{inc}|+|E_{outc}|{)}^2}{2\cdot |E|}}{|E|}$
     • 应用：衡量社区间重叠的程度，重叠度越低，社区质量越好。

FBCD方法通过结合这些质量度量，并使用TOPSIS（Technique for Order of Preference by Similarity to Ideal Solution）方法来聚合多个标准，从而选择最佳的社区结构。TOPSIS方法通过比较每个社区与理想解和负理想解的接近程度来确定社区的优先级。

总的来说，FBCD方法通过利用最大匹配来减少搜索空间，并结合多个质量度量来评估和选择最佳的社区结构，从而在具有节点属性的社交网络中有效地检测社区。

与传统的社区检测算法相比，FBCD算法具有以下优点：

• 算法不需要处理所有存在的边，因此可以减少搜索空间。
• 算法依赖于质量分数优化，这使得它可以适应不同的社区定义和用户需求。
• 算法使用了多指标决策分析方法TOPSIS，能够更准确地评估社区的质量。
  

3. 实验设计

本文主要介绍了对FBCD算法的性能评估和与其他算法的比较实验。实验使用了20个不同的真实世界网络数据集，并使用了多种质量指标来评估算法的表现，包括模度、导通性和密度等。在实验中，作者将FBCD算法与MDL-GREEDY、LPAb+和linkComm等算法进行了比较，并分析了它们在不同数据集上的表现。实验结果表明，FBCD算法在所有数据集中都表现出色，尤其是在处理大规模数据时比其他算法更快。此外，实验还展示了FBCD算法在处理复杂网络结构时的有效性，以及它能够产生高质量的社区检测结果的优点。

4. 总结

值得精读
本文提出了一种新的社区结构定义，并基于此设计了一个名为FBCD的算法来发现社区结构。作者进行了广泛的基准测试，证明了社区结构存在于各种领域的现实网络中，并且该算法比现有的社区检测方法（如基于模块度的方法、最小描述长度方法和链接分区方法）表现更好。此外，文章还探讨了未来的研究方向，包括考虑其他类型的二分图以及在分布式框架Spark下实现等。
本文提出了一个新的社区结构定义，该定义强调了社区结构的内部紧密性和外部分离性。基于这个定义，作者设计了一个名为FBCD的算法来发现社区结构。该算法使用了一种新颖的迭代方法，通过不断调整节点之间的连接权重来优化社区结构。这种方法相对于传统的基于模块度或最小描述长度的方法具有更高的准确性和效率。

5. 局限性

在未来的工作中，可以考虑将该算法应用于更广泛的数据类型，例如动态网络或带权网络。此外，可以在分布式计算框架Spark上实现该算法，以处理更大规模的数据集。还可以进一步研究如何将该算法与其他社区检测方法相结合，以提高其性能和准确性。