本文共字，预计阅读时间。

“物以类聚，人以群分”，具有相似属性的人往往会形成亲密的小圈子，圈子内部成员之间联系紧密，而圈子与圈子之间的联系相对稀疏。在社交网络中检测出不同社区结构对于风控信息传播、团伙欺诈检测具有重要作用。利用社区内的有效信息对于社区内缺失信息的节点具有很好的补充作用；在反欺诈领域会存在犯罪分子发现某些平台的风控漏洞，就会集中作案，以期短时间内获得巨额利润，呈现出明显的团伙特征。

复杂网络中的社区发现过程从本质上讲就是将复杂网络中的节点划分为大小不一子图的过程，其中子图中节点之间的联系紧密，而子图与子图之间的联系相对稀疏。占融数科通过对社区发现的研究，总结了经典算法如下：

传统算法

传统的社区发现算法包括图分割算法（Graph partitioning），层次聚类算法（Hierarchicalclustering），分割式聚类（Partitional clustering），谱聚类（Spectral clustering）等。图分割算法将社区发现问题定义为将网络中的节点分配到g个已经预先定义好规模的社区中去，并使处在社区间的边数最小。社区间的边数称为割值（cutsize）。图分割算法必须提前指定社区的个数，因为如果我们只是以最小割值为目标进行划分而不考虑社区个数，那么所有节点会形成一个大社区，因为此时割值为0。我们同样必须提前指定社区的大小规模，否则最有可能的结果是节点度最低的节点会与其余节点分离开来。Kernighan等人受到电路元器件在电路板上布局的思路启发提出了Kernighan-Lin算法，算法流程大概是最优化一个增益Q函数，增益函数Q 被定义为模块内部的边数与模块之间的边数差值。另外一个著名的分割算法是谱分割算法，它是基于拉普拉斯矩阵的谱属性来进行社区划分。我们可以使用Lanczos算法进行快速谱二分割。Flake等人使用最大流算法来对WWW网中的网页进行社区划分。图分割算法并不适合进行网络社区划分，因为我们需要提前知道社区的数量甚至是社区的规模，而从原理上说这些先验知识我们一般都不知道。

一般情况下我们都不知道网络要被分割的社区个数，这种情况下图分割算法就不能使用。网络往往具有层次结构，也就是说会呈现出不同粒度的聚类节点，小的聚类集合可能被包含在大的聚类集合中，大的聚类集合也可能被更大的聚类集合包含。层次聚类算法经常出现在社会网络分析，生物学，工程学等领域，层次聚类算法的目的是识别出具有较高相似度的节点集合，它有两种类别：凝聚算法，不断合并相似度较高的节点；分裂算法，不断地移除相似度较低的节点对对应的边。这两类都是最优化过程，凝聚算法是自底向上进行的，分裂算法是自上而下进行的。

分割式聚类算法是另一种流行的数据聚类算法，这里也需要提前指定聚类的个数k。每一个节点可以映射到一个度量空间中去，因此每个节点都是度量空间中的一个点，我们可以为一个节点对指定一个空间距离函数。这个距离函数表示了节点之间的相似度。而算法的目的就是将节点分到k个聚类中，最大或者最小化给定的损失函数。常用的函数有Minimumk-clustering表示聚类的直径，k-clustering sum聚类中样本点之间的平均距离等。一些作者将分割式聚类算法引入到网络聚类领域。谱聚类算法是将一些初始的节点集合转移到样本空间中去，这种转换可以使原始节点集的聚类属性更加明显。Donath和Hokmann利用邻接矩阵的特征向量进行图分割，同年Fiedler 提出拉普拉斯矩阵的第二小特征值对应的特征向量可以对网络进行有效具有的且具有更小割值的二分割。

分裂算法

对于识别网络中的社区问题，另一个简单的思路是将处在两个社区之间的边检测出来并将其删除，以使社区与社区彼此不相连。这也是分裂算法的基本原理。现在问题的关键点就是找到处在社区间边的共有属性，不同的算法也因此提出。其中最著名的一个算法是由Girvan和Newman提出的GN算法，GN算法使用边中心度值的方法来挑选社区间的边。他们考虑了三种不同的边中心度定义：边介数（Edgebetweenness）、随机游走介数（Random-walkbetweenness）、电流介数（Current-flow betweenness）。边介数指的是所有节点对间的经过这条边的最短路径总个数，网络中计算所有边的边介数的复杂度为，稀疏网络上为，算法整体的复杂度为，稀疏网络上为。随机游走介数是指一个随机游走者在沿着网络结构运行时经过这条边的频率，而网络中计算所有边的随机游走介数的复杂度为，稀疏网络上为。另外一种思路是将网络当作一个电路网络，每个边之间都有单位电阻，如果在某一节点对加上电压差，每个边就会有一对应的电流值。如果对所有可能的节点对都实施上述步骤，则电流介数就是边的电流均值，算法整体复杂度为，稀疏网络上为。实际应用结果表明三种算法中，边介数性能要优于其余两种算法。为了加快算法运行效率，降低计算复杂度，Wilkinson等人提出了GN算法的改进算法。Chen等人指出在计算边介数过程中考虑所有可能的最短路径会导致非均衡划分，并提出只计算非冗余路径的改进思路。

模块度最优化算法

模块度最优化算法是基于较高的模块度值对应较好的网络划分这一假设。因此，对于给定的网络，最大模块度值对应的网络划分应当是最优或者较优的。当前大多数最流行的社区发现算法都是基于这个思路展开的。但是由于网络划分的可能情况非常多，即使是对于较小的网络要想彻底最优化模块度也是不可能的。Brandes等人也从理论上证明模块度最优化是NP完全问题。因此一些近似最优算法就被提出，以便在合理的时间内得到结果。我们将重点介绍三种常用的近似最优算法：贪心技术、模拟退火、极值最优。

第一个模块度贪心优化算法是由Mark Newman提出的FN算法。它是一个凝结层次聚类算法，算法首先将所有的节点当作孤立的节点，然后不断地将两个节点合并，以使模块度不断增大。该算法总体复杂度为，稀疏网络上为，相比于分裂算法复杂度较低，可以在较大规模网络上运行。为了进一步降低算法复杂度，Clauset等人使用max −heaps数据结构，来减少一些无用操作，该算法总体复杂度为，d是算法得到的树状图深度。针对贪心优化算法会牺牲小社区而形成较大社区的问题，Danon提出归一化模块度变化ΔQ以得到更佳的模块度值。针对权值网络，Blondel提出另外一种贪心优化算法，Louvain算法，将算法流程分为合并社区以及重构网络两个过程，由于该算法只使用网络局部信息，因此算法复杂度很低，为O(m)，适用于大规模网络的社区发现，且该算法效果要优于前面几种算法。模拟退火算法是一种概率化最优化过程，Guimera首次将其应用到了社区发现问题。该算法包含两类移动过程：局部移动，随即挑选节点然后再从一个社区交换到另外一个社区；全局移动，将社区进行合并或者分割。该方法的结果非常接近真实的模块度最优值，但是复杂度很高，只能在节点个数小于104的网络上使用。

动力学算法

同步性是在交互系统中经常出现的一种自然现象。在一个同步的状态下，系统中的单元处于相同或者相似的状态。Arenas将网络节点类比为具有随机初始状态的振子，将边类比为振子与其邻居节点之间的相互作用，将同步性应用到了社区发现问题上。标签传播算法也可以应用到社区发现上来，Raghavan将网络中的节点赋予单一标签，然后根据传播规则来更新自身标签，提出LPA算法。这一过程从社会学的角度更容易理解，将节点当做一个人，边为人与其亲密好友之间的交互关系，标签则是这个人对某一特定事物的观点，在该人与其好友进行交互的过程中，人会接受来自其亲密好友的观点，同时也将自己的观点传给其亲密好友，最后具有相同观点的人形成一个社区。该算法复杂度为O(m)。

---

作为一家金融科技公司，融360|简普科技(NYSE:JT)成立于2011年10月，是独立开放的金融产品搜索、推荐和服务平台。2017年11月16日，融360旗下简普科技(NYSE:JT)在美国纽约证券交易所上市。

数字金融服务平台于2015年5月上线，通过人工智能、云计算等技术，为银行、持牌消费金融公司、保险等金融机构提供行业领先的数字金融服务。数字金融服务平台贯穿智能营销、智能信审、贷中监控、贷后管理等全流程业务线条，提供资产对接、流程设计、风险控制、系统实施、运营管理等服务，帮助金融机构持续提升运营能力、加速数字化转型。2020年，该平台正式命名为“占融数科”。

目前，融360|简普科技旗下占融数科的信息安全管理和服务、过程组织、AI研发、项目管理等能力均达到先进水平，获得了国际权威信息安全管理体系ISO27001认证、质量管理体系ISO9001认证和国际软件领域认证机构颁发的CMMI3级资质证书。累计服务数千家金融机构，参与超过亿次信贷决策，为千亿资金的安全提供有力保障。

[Source]

本文系未央网专栏作者发表，属作者个人观点，不代表网站观点，未经许可严禁转载，违者必究！首图来自图虫创意。

本文为作者授权未央网发表，属作者个人观点，不代表网站观点，未经许可严禁转载，违者必究！首图来自图虫创意。

本文版权归原作者所有，如有侵权，请联系删除。首图来自图虫创意。