论文部分内容阅读
摘 要：从社会网络中发现社会群体是当前社会网络研究的一个热点，社群发现的结果可被应用于商业营销和群体行为建模等诸多领域。本文对各种社群聚类算法进行分析与总结，用GN算法和网络效率（NE）概念解决基于通讯数据的社群聚类。将此分类应用于信息传播，设计出投放信息的方案来达到较佳的传播效果。
关键词：GN算法 网络效益 深度优先搜索 集群分类
一、算法分析与比较
复杂网络社群发现的算法有很多，常用的算法有这样几种算法：Kemighan—Lin算法、分级聚类算法、GN算法、极值优化算法等等。根据文献，我们知道这四种算法各有优势和劣势。我们就这四种算法进行比较，然后找出适合解决我们当前问题的算法。
Kernighan-Lin算法思路简单，很容易理解，但是其中存在着一些问题和缺陷。首先，在社群划分之前要求事先知道两个社群的大小，否则得出的结果误差比较大；然后，这种方法是一种二分方法，所以在划分之前要知道网络中社群的数目，来确定循环的终点。
分级聚类算法与Kernighan-Lin算法相比，可以在不需要事先知道网络中社群的结构和社群数量的情况下对网络进行社群结构的划分，而且取得了不错的结果。但是，这种算法也有其不足之处，首先就是这种算法并没有给出社群划分的度量标准，其次就是这类算法在对网络进行划分时，会将一些节点丢失，导致划分误差较大，还有就是在合并数据块时，无法保证数据块合并的合理性。
GN算法，移除介数最高的边然后重新计算边的介数是该算法中最重要的部分，而且在边移除的过程中，引入模块度Q来作为分割好坏的度量，从而选择最佳的社群划分。自GN算法推出之后，很多研究者使用该算法对不同的网络数据进行测试，得到了一系列很好的结果，包括邮件网络、科研合作网络、人类社交网络等。但是GN算法也存在一些问题，其中最突出的问题就是时间复杂度太高。
极值优化算法可以快速准确的划分出网络中的社群结构，但是该算法同样存在一些问题：首先就是网络初始的划分很容易影响算法的最终结果，划分的错误将出现很大的偏差；其次，算法在运行的过程中，可能只是得到局部的划分最佳，而无法达到全局的划分最佳，因为该算法采用贪心原理，只是在每一步中选取最佳的结果，但是最终的结果也许不是最佳；还有就是网络的模块度也许会持续的增长下去，直到划分出N个社群结构，因此，算法在何时结束无法进行判定。
根据上面的分析，我们可以看到，只有GN算法能得到较准确的结果，在对网络进行划分时，其划分误差较小，还有在合并数据块时能够保证数据块合并的合理性，但是GN算法时间复杂度较高，由于本文计算的数据并不是很庞大，所以这里应用GN算法来实现集群分类是最优之选。
二、GN算法与网络效益
1.GN算法。GN算法是一种使用分裂思想的算法，其基本思想是逐渐寻找和排除具有介数最大的边，直到网络被分成一个个的单元。而通过计算可以得出社群之间边的介数比社群内部边的介数高，因此可以通过逐步移除网络中边介数较高的边，实现对网络的分割。其算法的基本步骤是：
（1）首先计算网络中所有边的介数。
（2）移除介数最高的边，然后计算移除边之后网络中所有边的介数。
（3）重复步骤（2），直到网络被划分成N个节点为止。
2.网络效益。对于网络G，其中含有N个点，K条边。现在引入网络效率的概念，来衡量整个网络的通行能力及节点之间传输信息的有效性。
假设网络中任意两点之间的信息传播是通过最短路径来传播的，则节点i到j的信息传播效率εij可以表示为i与j之间最短路径的倒数（即最短路径越长，信息传播效率越低，反之越高）。而整个图的信息效率则定义为图中任意两点之间的信息传播效率的平均值，用NE（G）表示。用公式表示如下：
三、模型建立
在一个社群中，为了投放一条信息，并使得信息传播速度快覆盖范围广，就要投放的节点多，并且该节点把信息传递给其他节点速度快。但就成本考虑，投放的点越少越好。这样投放信息节点的数量和位置就在这里得到了解决。首先通过GN算法進行初步分群，确定投放节点数量，即所分子群的数量。然后通过网络效益的概念找出每个子群体中网络效益最大的节点作为投放的信息的节点。至此即能保证信息传播的覆盖面和传播速度，也能降低成本。这就是本文整个模型的建立基础。
有了GN算法和网络效益的概念后，我们需要一个模型能把给定的社群进行分群，本文采用C语言程序将给定的社群进行分群，具体的做法如下：
1.建立邻接矩阵并通过GN算法实现初步分群：
（1）首先，将给定的数据抽象到邻接矩阵中，即建立一个临界矩阵表示整个社群网络。
（2）GN算法的实现：①求最短路径。②计算介数。③删除介数最大的边直至模块化函数的模块化值最大。④深度优先搜素算法输出分群后的社群。
分群结果可抽象为如图3-1所示：
2.通过网络效益的概念进一步分群：
（1）根据网络效益的计算公式，用C语言程序实现算法，计算出每个点的网络效益，并按网络效益的大小依次输出各个节点。
其网络效益最大的节点即为一个群体，剩下的群里即为另外一个群体。分群结果可抽象为如图3-2所示：
四、模型应用
通过分析整理某营业部近三个月的内部通讯记录，建立出36*36邻接矩阵，并抽象出整个社群网络如图4-1所示：
图4-1中，用1-36号对人名进行编号，每个节点表示一个个体，节点上的权值表示个体间通话时长导数的10000000倍（扩大倍数方便计算）。所建立的邻接矩阵节点与权值也是类似的方法表示。
然后利用上文所建立的模型，也就是利用编写好的C语言程序，将得到的邻接矩阵代入其中计算出所需要的参数。 首先利用GN算法程序，可得到如图4-2运行结果。从图中，我们可以清楚的看到，当程序运行停止后，经过深度优先搜素算法出现兩个断点，最终准确得到三个群体。而这三个群体分别是：
A：2，3，4，5，6，7，8，9，10，16，17
B：1，11，12，13，14，18
C：15，19，20，21，22，23，24，25，26，27，28，29，30，31，32，33，34，35，36。
然后利用计算网络效益的C语言程序，分别计算每个群体中各个节点网络效益。即首先建立各个群体的邻接矩阵，然后带入到程序中计算，分别得到如图4-3（a）、图4-3（b）、图4-3（c）运行结果。
从运行结果中，我们可以看出，如果我们要投放信息，其投放的信息节点有三个，分别是1、2、15。其最终把36个个体分群如图4-4所示。
另外考虑通讯位置、时间、通话频率等因素，我们同样可以利用前面所建立的模型对每个因素进行一次集群分类。
五、结语
本篇论文的主要工作是在前人的研究基础上，对传统的GN算法加以运用及改进，并结合网络效率（NE）的计算，实现社群高效快速的发现。在理解GN算法和网络效率计算方法的基础上，利用具体的数据进行社群划分，先通过简单的数据模型进行算法和方法的测试，然后在此基础上运用复杂网络社群进行分群，得到较为合理的划分。
最后，感谢江汉大学数计学院数学建模实验室！
参考文献：
[1]于洋洋.基于并行K-MEANS聚类分析的社群发现算法研究[D].东北大学，2012.
[2]NVIDIA Corporation.NVIDIA CUDA C Programming Guide[R]，Version 4.0，2011.
[3]Newman，Girvan.Finding and evaluating community structure in networks[J]，Phys Rev E，2004，69（2）：026113.
[4]林有芳，王天宇，唐锐，周元伟，黄厚宽.一种有效的社会网络社群发现模型和算法[J]，计算机科学与发展，2012，49（2）：337-345.
关键词：GN算法 网络效益 深度优先搜索 集群分类
一、算法分析与比较
复杂网络社群发现的算法有很多，常用的算法有这样几种算法：Kemighan—Lin算法、分级聚类算法、GN算法、极值优化算法等等。根据文献，我们知道这四种算法各有优势和劣势。我们就这四种算法进行比较，然后找出适合解决我们当前问题的算法。
Kernighan-Lin算法思路简单，很容易理解，但是其中存在着一些问题和缺陷。首先，在社群划分之前要求事先知道两个社群的大小，否则得出的结果误差比较大；然后，这种方法是一种二分方法，所以在划分之前要知道网络中社群的数目，来确定循环的终点。
分级聚类算法与Kernighan-Lin算法相比，可以在不需要事先知道网络中社群的结构和社群数量的情况下对网络进行社群结构的划分，而且取得了不错的结果。但是，这种算法也有其不足之处，首先就是这种算法并没有给出社群划分的度量标准，其次就是这类算法在对网络进行划分时，会将一些节点丢失，导致划分误差较大，还有就是在合并数据块时，无法保证数据块合并的合理性。
GN算法，移除介数最高的边然后重新计算边的介数是该算法中最重要的部分，而且在边移除的过程中，引入模块度Q来作为分割好坏的度量，从而选择最佳的社群划分。自GN算法推出之后，很多研究者使用该算法对不同的网络数据进行测试，得到了一系列很好的结果，包括邮件网络、科研合作网络、人类社交网络等。但是GN算法也存在一些问题，其中最突出的问题就是时间复杂度太高。
极值优化算法可以快速准确的划分出网络中的社群结构，但是该算法同样存在一些问题：首先就是网络初始的划分很容易影响算法的最终结果，划分的错误将出现很大的偏差；其次，算法在运行的过程中，可能只是得到局部的划分最佳，而无法达到全局的划分最佳，因为该算法采用贪心原理，只是在每一步中选取最佳的结果，但是最终的结果也许不是最佳；还有就是网络的模块度也许会持续的增长下去，直到划分出N个社群结构，因此，算法在何时结束无法进行判定。
根据上面的分析，我们可以看到，只有GN算法能得到较准确的结果，在对网络进行划分时，其划分误差较小，还有在合并数据块时能够保证数据块合并的合理性，但是GN算法时间复杂度较高，由于本文计算的数据并不是很庞大，所以这里应用GN算法来实现集群分类是最优之选。
二、GN算法与网络效益
1.GN算法。GN算法是一种使用分裂思想的算法，其基本思想是逐渐寻找和排除具有介数最大的边，直到网络被分成一个个的单元。而通过计算可以得出社群之间边的介数比社群内部边的介数高，因此可以通过逐步移除网络中边介数较高的边，实现对网络的分割。其算法的基本步骤是：
（1）首先计算网络中所有边的介数。
（2）移除介数最高的边，然后计算移除边之后网络中所有边的介数。
（3）重复步骤（2），直到网络被划分成N个节点为止。
2.网络效益。对于网络G，其中含有N个点，K条边。现在引入网络效率的概念，来衡量整个网络的通行能力及节点之间传输信息的有效性。
假设网络中任意两点之间的信息传播是通过最短路径来传播的，则节点i到j的信息传播效率εij可以表示为i与j之间最短路径的倒数（即最短路径越长，信息传播效率越低，反之越高）。而整个图的信息效率则定义为图中任意两点之间的信息传播效率的平均值，用NE（G）表示。用公式表示如下：
三、模型建立
在一个社群中，为了投放一条信息，并使得信息传播速度快覆盖范围广，就要投放的节点多，并且该节点把信息传递给其他节点速度快。但就成本考虑，投放的点越少越好。这样投放信息节点的数量和位置就在这里得到了解决。首先通过GN算法進行初步分群，确定投放节点数量，即所分子群的数量。然后通过网络效益的概念找出每个子群体中网络效益最大的节点作为投放的信息的节点。至此即能保证信息传播的覆盖面和传播速度，也能降低成本。这就是本文整个模型的建立基础。
有了GN算法和网络效益的概念后，我们需要一个模型能把给定的社群进行分群，本文采用C语言程序将给定的社群进行分群，具体的做法如下：
1.建立邻接矩阵并通过GN算法实现初步分群：
（1）首先，将给定的数据抽象到邻接矩阵中，即建立一个临界矩阵表示整个社群网络。
（2）GN算法的实现：①求最短路径。②计算介数。③删除介数最大的边直至模块化函数的模块化值最大。④深度优先搜素算法输出分群后的社群。
分群结果可抽象为如图3-1所示：
2.通过网络效益的概念进一步分群：
（1）根据网络效益的计算公式，用C语言程序实现算法，计算出每个点的网络效益，并按网络效益的大小依次输出各个节点。
其网络效益最大的节点即为一个群体，剩下的群里即为另外一个群体。分群结果可抽象为如图3-2所示：
四、模型应用
通过分析整理某营业部近三个月的内部通讯记录，建立出36*36邻接矩阵，并抽象出整个社群网络如图4-1所示：
图4-1中，用1-36号对人名进行编号，每个节点表示一个个体，节点上的权值表示个体间通话时长导数的10000000倍（扩大倍数方便计算）。所建立的邻接矩阵节点与权值也是类似的方法表示。
然后利用上文所建立的模型，也就是利用编写好的C语言程序，将得到的邻接矩阵代入其中计算出所需要的参数。 首先利用GN算法程序，可得到如图4-2运行结果。从图中，我们可以清楚的看到，当程序运行停止后，经过深度优先搜素算法出现兩个断点，最终准确得到三个群体。而这三个群体分别是：
A：2，3，4，5，6，7，8，9，10，16，17
B：1，11，12，13，14，18
C：15，19，20，21，22，23，24，25，26，27，28，29，30，31，32，33，34，35，36。
然后利用计算网络效益的C语言程序，分别计算每个群体中各个节点网络效益。即首先建立各个群体的邻接矩阵，然后带入到程序中计算，分别得到如图4-3（a）、图4-3（b）、图4-3（c）运行结果。
从运行结果中，我们可以看出，如果我们要投放信息，其投放的信息节点有三个，分别是1、2、15。其最终把36个个体分群如图4-4所示。
另外考虑通讯位置、时间、通话频率等因素，我们同样可以利用前面所建立的模型对每个因素进行一次集群分类。
五、结语
本篇论文的主要工作是在前人的研究基础上，对传统的GN算法加以运用及改进，并结合网络效率（NE）的计算，实现社群高效快速的发现。在理解GN算法和网络效率计算方法的基础上，利用具体的数据进行社群划分，先通过简单的数据模型进行算法和方法的测试，然后在此基础上运用复杂网络社群进行分群，得到较为合理的划分。
最后，感谢江汉大学数计学院数学建模实验室！
参考文献：
[1]于洋洋.基于并行K-MEANS聚类分析的社群发现算法研究[D].东北大学，2012.
[2]NVIDIA Corporation.NVIDIA CUDA C Programming Guide[R]，Version 4.0，2011.
[3]Newman，Girvan.Finding and evaluating community structure in networks[J]，Phys Rev E，2004，69（2）：026113.
[4]林有芳，王天宇，唐锐，周元伟，黄厚宽.一种有效的社会网络社群发现模型和算法[J]，计算机科学与发展，2012，49（2）：337-345.