基于通讯数据的社群聚类
摘要
大数据时代的来临使得许多不可能成为了现实。数据分析和数据挖掘技术成 功地在多个重大领域取得了巨大成功。现已有部分人群通讯数据，对人群进行社群分类和相关识别。
针对问题一, 本文运用改进的K -MEANS 算法对图一中无向图网络的节点
9
进行分类。首先，计算出整个网络的聚集系数为，并对网络效率及各边信息
10
中心度计算，由此推导得出节点关联度及关联矩阵。最终，建立模型得出分类结果：共分为三类，一类为1号节点，二类为2,3,4号节点，三类为5,6号节点。
针对问题二，本文采用基于节点相似度的社团结构划分算法对图二的无权有向网络中的节点进行划分。首先把网络中的每个节点看做一个社团，基于此对模块度矩阵进行分析，把尺度伸缩变换引入到模块度矩阵，得到标准化模块度矩阵，将其特征值按降序排列。本文选择前两个最大特征间隔来确定较准确确定社团划分为两个。接着，对图二网络中各节点进行最短路径分析及相似度计算，得出分类结果：共分两类，一类为1,2,3，二类为4,5。而后运用模块度函数对划分结果进行验证优化，与原划分结果一致。
针对问题三, 本文对问题一、二中所得模型做出综合实际化改进对个体进行分群。为简化分类难度，先将所有个体进行编号，后运用题目所给数据使用MATLAB 软件绘制出所有个体间的通信拓扑网络，得出1,2,3,4号个体通话人数多，联系范围广的初步结论，最后又以个体成员主叫次数、总通话时长、主叫拨打人数进一步量化分析，得出分群结果：一类为:3,4,5,6,7,8,9,10,11,12,13, 14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,30,31,32,33,35,36；二类为20, ；三类为1,2,34。
针对问题四，本文对附件数据分析发现信息的传播率主要受传播主体的传播能力和传播客体的被叫概率影响，便挑选传播能力较高、被叫率较高的个体作为信息投放点，进行多次模拟实验，得出，定向对节点17,18,12,13,15,10,23,11, 26,20进行信息投放时，能以最低的信息成本得到最大的信息覆盖率。
针对问题五, 本文对问题四信息传播概率模型进行改进，从多个传播主体、传播课题和传播路径三方面提取信息传播的影响因子，建立综合模型。并找出显著特征因子，按其权重依次为：节点间结构相似度、用户对信息的传播兴趣以及节点间是否相互通话。
关键词： 改进K -MEANS 算法 广度优先搜索遍历算法 社团结构划分算法 聚类分
析 端到端信息传播概率模型
一、问题重述
大数据时代的来临使得许多不可能成为了现实。现有部分人群的通讯数据，试对人群进行社群分类和相关识别。社群分类中往往将数据表示为图的形式。
（1）图一中，六个点分别表示六个个体，点与点间的边表示个体间的联系，并且是无向图，试就图中信息，分析区分个体差异，对个体进行初步识别，实现分群。
（2）图二中，同样五个点表示五个个体，此时为有向图。在识别个体的同时，希望能进一步刻画任意两点之间的相似关系，从而达到“ 物以类聚，人以群分”的目的。
（3）附件中给出某营业部近三个月的内部通讯记录。结合并完善问题 1， 2中的数学模型，对其进行分析和识别，实现个体的分群，并得出相应的结论。
（4）假设每投放一个节点的信息成本为m, 信息在传播过程中每经过一个节点, 都有 10%～50%的终止传播概率, 试以附件一中所给记录, 计算最少要在哪些节点投放信息就可以达到最大的信息传播覆盖率。
（5）上述问题中，实际忽略了很多有用的信息，如通讯的位置、时间、通话频率等。请再考虑位置、时间等多种因素建立综合的数学模型，挖掘更多的信息。如有需要，可以自行补充数据，验证自己的模型，得出相应结论。
二、模型假设
（1）假设所有边的联通不受其他边影响。 （2）假设主叫呼叫不受限制。
（3）假设所给数据可代表一般情况。 （4）假设网络中任意边不会中断。 （5）假设任意边长度相等。
三、符号声明
C (i )
聚集系数
NE (G ) 信息传播效率
C ij
边的信息中心度
关联度
nodelink (i , j )
L 关联度矩阵
DIS (i , j )
节点相异度
t jk
平均最短路径长度
similarity (i , j ) 节点相似度
Q 模块度
A (i , j )
领接矩阵
u 矩阵特征值
四、问题一的求解
4.1基于改进K-MEANS 算法的网络分类 4.1.1网络的定义与符号
图论是复杂网络进行精确处理的自然框架，且复杂网络在形式上可以用图来表示。无向图G=(N，E)由集合N和E组成，且N≠E, 集合E是由集合N中元素的无序对构成的集合。集合N={n1, n2, ⋯nn}中的元素是图G的节点，集合E={e1, e2, ⋯ek}中的元素是图的边。集合N和E中的元素个数分别由n和k表示。假设矩阵A是N×N的方阵，而无向图G =(N , E )可以用邻接矩阵A 完全描述，则矩阵中的元素为
⎧1, e ij ∈E
a ij =⎨i , j ∈(1, n )
⎩0, other (4.1)
4.1.2聚集系数
在复杂网络中，通常用点聚集系数来表示节点间的聚集情况。某节点的点聚集系数可表示为该节点的所有邻接点之间实际连边数与所有可能存在的连边数的比值。整个网络的聚集系数可以用网络中所有节点的点聚集系数平均值来表示，说明了整个网络的聚集性。可表示为公式（2）
C(i ) =
E (i )
（4.2）
k i k i -1/2
显然，点聚集系数表达了节点的近邻之间也是近邻的程度。根据之前的描述，若网络中每个节点的点聚集系数都被计算出来，则整个网络的聚集系数就可表示 为所有C (i )的平均值。网络ξ的聚集系数：
1N
（4.3） C ξ=∑C (i )
N i
当图中的节点为1时，其邻接点为2,3,4,5,6五个节点，则在五个节点之间可能的连接边会有10条，但实际只有（2,3），（2,4），（3,4），（5,6）四条边，
2
因此可以根据公式（4.2）算出节点的聚集系数为：，由此可计算出其他节点
5
的聚集系数。当图中的节点为2，3，4，5，6时，各个节点的聚集系数分别为1，
9
1，1，1，1。进而根据公式（4.3）计算出整个网络的聚集系数为：。
10
由于节点的邻接点之间实际存在的边不会大于可能存在的最大值，因此无论是点聚集系数还是整个网络的聚集系数，其范围都是[0,1]。当某点的度为0或1时，或者当节点的邻接点之间相互独立时，该节点的点聚集系数为0，这表示该节点与其邻接点构成的连通分量是松散的。当某点的点聚集系数为1时，则表示该点与其邻接点之前构成的连通分量是完全图，具有高聚集度。
由于聚类系数2，3，4，5，6相等，因此可将六个节点初步分为2类，分别为节点1一类，节点2，3，4，5，6一类。 4.1.3网络效率NE及边信息中心度
对于网络，其中含有6个点，9条边。现在引入网络效率和边信息中心度的概念，来衡量整个网络的通行能力及节点之间传输信息的有效性。假设网络中任意两点之间的信息传播是通过最短路径来传播的，则节点到的信息传播效率可以表示为与之间最短路径的倒数（即最短路径越长，信息传播效率越低，反之越高）。而整个图的信息效率则定义为图中任意两点之间的信息传播效率的平均值，用表示。用公式表示如下：
NE (G ) =
i ≠j ∈G
∑ε
ij
/n (n -1)=
i ≠j ∈G
∑(1/d (i , j ))/n (n -1)
（4.4）
由问题一无向图可知节点数n 为6，
i ≠j ∈G
∑(1/d (i , j ))表示所有最短路径倒数
之和，且d (i , j )与d (j , i )不重复使用，所表示的结果如下表4.1.3-1：
经计算得
i ≠j ∈G
∑
(1/d (i , j ))为12，因此由公式（4.4）得NE (G ) 为
2。 5
根据以上网络效率的定义，现在定义边的信息中心度。边的信息中心度则定义为移除该边后对整个图的网络效率的影响，用公式表示如下：
C ij =∆NE /NE =NE (G )-NE (G ' )/NE (G )
(
) （4.5）
即移除某条边之后整个网络效率值的减少量与未移除该边时网络效率值的比值。NE (G ' )中d (i , j )表示除d (i , j )这条边之外的一个节点与其他节点的最短路径。d (1,2)表示如下表4.1.3-2：
i ≠j ∈G
经计算得
∑
(1/d (i , j ))为
675
，由公式（4.5）可得C 12为。其他C ij 计算672
同上，得到结果如下表4.1.3-3：
通过分析可以得出社群之间边的信息中心度比社群内部边的信息中心度大。即当删除社群之间的边时，对整个网络效率值的影响比删除社群内部的边时对网络效率的影响大。由于2，3，4所得边信息中心度相等，5，6的边信息中心度相等，因此可以在原先的基础上将六个节点分为3类，分别为节点1一类，节点2，3，4一类，节点5，6一类。 4.1.4节点关联度及关联度矩阵
关联度也可以理解为两个节点之间相近的程度，即两点之间最短路径越短，其关联度越大，反之若两点之间最短路径越长，其关联度越小。通过分析可知，对于网络中相邻的两个点与其最短路径为，即为它们之间的一条边。若它们之间边的信息中心度比较小，则它们之间的节点关联度比较大。因此对于相邻的两个节点与的关联度，用公式表示则可以表示成
nodelink (i , j )=1-C ij
（4.6）
由表格经公式（4.6）可得关联度，如下表4.1.4-1：
nodelink (i , j )表示两点的关联度。而对于不相邻的节点之间的关联度，由于两点之间的最短路径至少为1，而且关联度会随着最短路径的变长而变小。此时，两点之间的关联度用公式可以表示为：
nodelink (i , j )=MAX ∏nodelink (i , j )
（4.7）
即不相邻两点之间的关联度为其最短路径上相邻节点关联度的乘积。因此可
737
以求出其他不相邻两点之间的关联度都为。
864
根据上面公式与可知，节点之间的关联度为
i j ⎧⎪1-C ij
nodelink (i , j )=⎨
⎪⎩MAX ∏nodelink (i , j )i j （4.8）
下面定义关联度矩阵，用来表示关联度矩阵。考虑到节点自身的关联度对社群结构的划分没有什么影响，因此现在统一将节点自身的关联度定义为该点的度。因此，根据节点之间的关联度，关联度矩阵中的元素用公式表示为
⎧⎪deg (i )L =⎨⎪⎩nodelink (i , j )
i =j
i ≠j
（4.9）
当i =j 时，矩阵的对应元素值为该节点的度, 即每个节点的度为1；当i ≠
j
表4.1.4-2 两点之间的关联度
该矩阵L 可以表示为：
⎡⎢1⎢⎢67⎢72⎢⎢67⎢72A =⎢
67⎢⎢72⎢11⎢⎢12⎢11⎢⎣12
67
[***********]37864
[***********]4737864
[***********]4737864
[***********][1**********]⎤12⎥⎥737⎥864⎥
⎥737⎥864⎥
⎥737⎥864⎥23⎥⎥24⎥⎥1⎥⎦
4.1.5 节点相异度
对于具有社团结构的无向网络，引入相异性指数来度量 2 个相邻节点同属一个社团的可能性大小，其依据是从节点i 到节点j 要经过的平均步数。用最短路径长度代替节点间的距离。
对网络中任何一个节点i ，集合{t i 1, t i 2,
, t i , i -1, t i , i +1,
, t iN }表示其他各节点到
节点i 的最短路径长度。若节点i 和节点j 可达(0≤p ij ≤1)，则节点相异度
DIS (i , )j 为：
DIS (
i , j )=
（5.0）
当节点i 和j 属于同一个社团时，节点i 到任一其他节点k (k ≠i , j )的平均最短路径长度t ik ，将与节点j 到节点k 的平均最短路径长度t jk 相近。当节点i 和j 属于同一个社团时，DIS (i , j )较小，反之较大。
由公式（5.0）计算得节点2,3和节点3,4和节点2,4的DIS (i , j )都为0，节点5,6的DIS (i , j )为0。
4.2 结论
显然，矩阵L 是对称矩阵。由关联度和关联度矩阵分析，发现了节点2，3，4之间存在一定的关系，节点5，6之间存在一定的关系，证明了边信息中心度分类的准确性。通过节点相异度分析出各个节点的社团，说明了节点2，3，4
一个社团，节点5，6一个社团。
综上所述，可以将六个节点分为3类，分别为节点1一类，节点2，3，4一类，节点5，6一类。
五、问题二的求解
5.1基于节点相似度的社团结构划分算法 5.1.1网络的定义与符号
首先给出算法中用到的一些概念。G (E,V )是一个有向无权图：
V ={1,2,3
n }是G 中的所有点的集合；E ={(i , j )i , j ∈V 是G 中的所有边的集合，
且V =m , E =n ; A 是其对应的邻接矩阵，如果节点v i 和v j 之间有路存在，A ij =1; 否则，A ij =0。
(1)节点共近邻
表示节点之间共同邻居的个数，用NNN 表示，其表示形式为：
NNN (i , j )=N (i :)⋂N (j :) (5.1) 其中, N 表示节点的邻居矩阵，N (i :)和N (j:)分别表示节点i 和j 的邻居集合，则NNN (i , j )是N (i :)和N (j:)有相同节点的个数。
(2)最短路径长度
表示从一个节点到另一个节点经过最少边的条数，用d 表示，d (i , j )则表示节点i 到节点j 的最短路径长度。
5.1.2节点相似度
如果两个节点属于同一个社团，那么这两个节点之间拥有较高的相似度，且这两个节点之间拥有较多的共同邻居，相似度度量主要依据节点之间的共同邻居，在节点之间的共同邻居基础上构造的相似度度量公式。而通过对复杂网络的结构特征研究发现，除了节点之间的共同邻居外，节点之间的最短路径长度也可以反映节点之间的相似度，即如果两个节点之间具有较小的最短路径，则这两个节点也具有一定的相似性，也有可能属于同一个社团。基于此思想，本文提出一个节点相似度度量公式，similarity (i , j )表示形式为:
⎧NNN (i , j )
, i ≠j ⎪
similarity =⎨d i , j ⎪A i , j
⎩(), i =j
（5.2）
5.1.3标准化模块度矩阵
把网络中的每个节点视为一个维度，利用降维的方法来获得网络拓扑的一个
简化表示，该简化表示下的每个维度对应一个社团。基于该思路，本文对模块度矩阵进行分析，把尺度伸缩变换引入到模块度矩阵，得到标准化模块度矩阵。根据标准化模块度矩阵的分析，一般选择模块度矩阵的最大特征值对应的特征向量对网络进行划分。将标准化模块度矩阵的特征值按降序排列，两个连续特征值之间的差值也就是特征间隔提供了一个有效的指标来确定适当数量的重要特征向量，重要特征向量的个数能够确定将要划分社团的个数，进而可以根据较大特征间隔对应的特征值所在的位置来得到将要划分社团的个数。本文选择前两个最大特征间隔来确定较准确的社团个数，利用这两个最大特征间隔对应的特征值所在的位置分别得到所对应的社团划分个数，根据节点相似度将网络划分成预先确定的社团个数, 例如一个网络的标准化模块度矩阵的第一个最大特征间隔在第2个和第3个特征值之间，则这个矩阵的重要特征向量个数为2, 该网络可以划成3个社团。计算这两个划分结果所对应的模块度Q 值，选择较大Q 值所对应的划分结果即为较优划分结果。第i 个特征间隔定义为u i -1-u i (2≤i ≤n )。SM 标准化模块度矩阵公式的表示形式为：
SM (i , j )=
A (i , j )-
D (i )*D (j )
（5.3）
其中A (i , j )表示网络的邻接矩阵, D (i )、D (j )分别表示节点i 和j 的度, m 表示网络的总通路数。 5.1.4模块度
模块度函数是评判社团结构划分结果优劣的效益函数，应用于复杂网络社团结构划分的各种算法中，模块度Q 值的大小对映了社团结构划分结果的好坏，一般来说实际中的网络Q 值在0.3~0.7这个范围之间，Q 值越大网络中的社团结构划分结果越好，Q 值最大为1。NG 模块度Q 值函数表示形式为：
^
Q =∑M l =1⎡l ii /L -(d i /2*L )2⎤
⎣⎦ （5.4）
其中l ii 表示社团i 内路的总数，L 表示网络中路的总数，d i 表示社团i 内的节点度之和。模块度是复杂网络中社团结构划分的目标函数，也是对社团结构评
价的依据，利用模块度函数可以很好的评价社团结构划分算法的优劣。
详细算法描述如下：
Input: Graph (G )的邻接矩阵A
Output: Graph (G )={G 1, G 2, G 3,
G k }
（1）根据标准化模块度矩阵的前两个最大特征间隔来分别确定将要划分社团的适当个数v 1和v 2; 主要分为5步，具体步骤如下所示:
① 根据公式（5.3）可以得出该网络的标准化模块度矩阵 SM 为： m=6。
② 该网络的标准化模块度矩阵可以用matlab 软件得到网络的特征值u 为：
{ 1.4077 + 0.5139i，1.4077 - 0.5139i， 0.7692 ，0.8154 ，0.6000} ③将特征值按降序排列，得到网络的降序排列特征值u 为：
{ 1.4077 + 0.5139i，1.4077 - 0.5139i，0.8154, 0.7692 ，0.6000} ④进而得到该网络的标准化模块度矩阵的特征值之间的特征间隔为： {0.0000, 0.5923- 0.5139i,0.0462, 0.1692}；
⑤最大特征间隔在第一个特征值和第二个特征值之间，则这个矩阵的重要特征向量个数为 1，根据较大特征间隔所对应的特征值的位置可以得到对应的社团个数为2个。
（2）根据节点之间的共同邻居个数和节点之间的最短路径长度，得到节点相似度矩阵similarity 。
问题二通过广度优先搜索算法求得，简称BFS 。BFS 是一种盲目搜索法，其系统地展开并检查图中的全部顶点。BFS 也是最简便的图搜索算法之一，其类似思想被Dijkstra 算法和Prim 算法采用。问题二求解图是一张由五个顶点组成的有向图，其中图中的每条边的权值都是1，求解从一个顶点出发依次到图中全部顶点的距离，使得图中所有的顶点都被访问过一次 ，如源头为v 1，搜索的顺序就是：v 2→v 3→v 4→v 5，由编码（附录2）结果如下表5.1.4-4：
v 2={4}。 （3）由（2）得，（1,2），（1,3）（1,5）相似度最高，得到v 1={1,2,3,5}，（4）求当社团个数为v 1和v 2时所对应的Q 值为0.4。
5.2 结果与分析
设图G 是一个由 5个节点，6 条路组成的无权有向网络，该网络具有明显的社团结构，按社团划分算法来分群具有一定的准确性和有效性。将本文算法应用于该网络上，对该网络进行社团划分，但结果仍存在不足。
根据对两点间的路径侧重点不同，把这些度量分为两大类：一类是以SR 为代表的度量，SR 计算图中两点相似度是基于人们这样的直觉：如果两个对象同时被相同或相似的对象所引用, 那么这两个对象是相似的，反映在网络上，用随机游走模型解释为：点a 和点b 的相似度是指两个冲浪者分别在点a 和点b 出发同步相对游走当且仅当第1次相遇的期望值，所示的路径称为逆向共同路径。
另一类是以PPR 为代表的包括RWR,Hitting time的度量。它们考虑了如图5.1所示的路径，点a 和点b 的相似度越高表示从点a 出发随机游走遇到点b 的概率越大，文中把如图5.1所示的路径称为同乡单向路径。
图5.1 同乡单向路径
从表5.1.4-5中可以看出，计算相似度时，各个节点的度的值为出度和入度的和，未具体考虑出度和入度的链接。
图5.2待求网络示意图
从图5.2中可以看出：(4,5)的SR 值为不为0，这是因为b 和d 之间存在一条逆向共同引用路径，图中的其他结点对之间不存在类似这样的逆向共同引用路径，因此，它们的SR 值都为0。与SR 不同的是，PPR 的值不具有对称性，即(a,b)和(b,a)的PPR 值是不同的；从v 1到v 4之间存在单向路径，所以对应的PPR 值不为0，而其他的结点对之间不存在这样的单向路径，所以对应的PPR 值为0。
从上面这个例子发现:SR和PPR 考虑的路径是不同的，有些结点对的SR 值非0而PPR 值却是0；反之亦然。有些结点对的SR 和PPR 值同时为0, 比如(2,1)
3), 与相似度similarity 计算结果可以得知: 和(1，v1，v2，v3相似相符; 但SR(1,4)为0，存在单路，导致v 4，v 5无法到达v 1，v 2; 且PPR （4，5）不为0，联通度大。通过以上分析和讨论可知以及实践应用表明，这两大类路径对结点间的相似度都很重要, 所以我们把实验结果修正为：v 1={1,2,3}，v 2={4,5}，此时Q 值为0.6，大于原划分时的Q 值（0.4），为最优解。
六、问题三的求解
6.1对通话记录的分析处理 6.1.1相关数据变量的简化
由于数据中存在字符与数值混杂情况，给分析造成一定麻烦，因此在进行数据分析前给予以下假设与简化：
（1） 对相关人员名字进行标号，用数字代替（具体分类见附录3）。 （2） 用网络拓扑图表示通话情况时，对主被叫关系予以忽略。 6.1.2通话网络构建
根据附件中三个月的通话记录数据以及节点和边的生成规则，利用MATLAB 软件（附录4）描绘出通话网络，得到如下网络关系图：
图6.1.2 通话网络示意图
从图6.1.2中可以看出，1，2，34等的节点连接网线较多，其聚类系数较高，节点关联度较好，所代表成员在这三个月内与较多人员进行过通话联系。13,17,18等节点连线较少，其聚类系数较低，节点关联度较差，代表成员在这三个月内联系的人员较少。由于网络较复杂，网络效率平均，每条边的信息中心度不显著。但此图无法分析出时间等其他较详细数据，并且由于相同的联系会被重复绘制而覆盖，得出信息有限。 6.1.3数据量化分析
在通信网中，主叫方发起主叫命令，呼叫建立，被叫方应答后通话产生。因此可知，主叫所占能动权重较大。以主叫次数为例，进行相关分析。通过matlab
表6.1.3-1中，明显看出，1,2,20,34各主叫次数均达到百分之十左右，属图6.1.3-2各成员主叫通话总时长
由各成员通话时长表格（附录5）绘图6.1.3-2，从图6.1.3-2可以看出，大部分成员主叫通话总时长都在200000秒以内，2号超过一百万秒，1，20,34这三个成员次之。33成员总时长在400000秒左右。
图6.1.3-3各成员主叫拨打人数
由各成员拨打时长表格（附录6）绘图6.1.3-3，从图6.1.3-3中可看出，大部分成员主叫只会拨打给4人左右，1,2,33，34拨打人数为15人左右, ，并可以得出，20号虽主叫通话次数多，时间长，但拨打人数少，与1,2,34等特征明显相反。
6.2基于现有数据分析后对成员分类情况
主叫次数占总主叫次数百分比超过8%以上，便称为主叫密集型人群；8%以下，称为主叫一般型人群。并可推知，1,2,34通话人数较多，联系范围广，可能与职业、性格等因素有关。
而后，通过对通话时长，拨打人数两方面进行观察，发现，20虽拨打次数多，通话时间长，但拨打人较为单一，推知其只善于和熟悉的人交谈，或者工作七、问题四的求解
问题四要求我们尝试定向对某几个节点进行信息投放，假设每投放一个节点的信息成本为 m,信息在传播过程中每经过一个节点, 都有 10%～50%的传播终止，即信息丢失的概率, 要求用附件1里提供的10000多条通话记录分析达到投放最少的节点覆盖最多的人群的最优决策，并求得哪些投放节点。
通过对数据分析我们发现信息的传播率主要受传播主体的传播能力和传播客体的被叫概率影响。为缩小信息投放节点的选择范围，假设初始通知了m 个人： （1）这m 个人必须在主叫中，次数越高，传播能力越强。对36个人的主叫次序排序，结果如下表：
由表可以直观的观察到A 1={18,17,20,16}，这4个节点传播能力最高模拟时优先投放这5个节点。
（2）除了这m 个人以外其他人在后续的通话记录中都得被通知至少50次才保证每个人都通知到，传播停止风险高的优先传播。对36个人的被叫概率排序，结果如下表：
观察上表，发现A 2={17,18,16,20}中四个点的被叫率突出，模拟时同祥优先考虑投放。
综合上述指标得到消息传递概率综合排序，如下表：
A 3={17,18,12,13,15,10,23,11,26},9个节点在被叫和主叫排序中均靠前，且
包括A 1, A 2要求的节点。所以m ≥9，且第一次模拟取m=9，得到结果2表格（附录7），实现用伪代码表示如下（具体见附录8）： /** 创建数组 **/
array message_count = int(37); array message_recv = int(37);
/** 初始化 设置初始通知的用户消息数为1 概率也直接为1**/ message_count[9]=1; message_recv[9]=1;
for (通话记录 order by time){
message_count[主叫]*0.5 传递给 message_count[主叫]; 7.2.1模型求解与结果分析
多次模拟，结果介于结果1和结果2之间：结果1里面是初始通知了这13个人，结果2是通知了9个人。
根据通话记录时间顺序，每打一个电话至少会向对方提供提供自身拥有的消息数量的50%。如下图，两个结果显示，结果1里面最终所有人都获得了这个消息, 结果2里面显示26号用户没有被任何人通知到。
图7.2.1-1 m=9分析结果
图7.2.1-2 m=13分析结果
确定m ∈[9,13], 结果1里面显示20号用户初始通知到了，其后用户能得到概率是97.74%，为使结果既满足m 值最小，且能把所有用户有覆盖以达到最大覆盖率，我们在m=10时，投放节点集合A 3={17,18,12,13,15,10,23,11,26 }中加入节点20，再次模拟发现此时所有节点都可以被传播到。
综上所述，定向对节点17,18,12,13,15,10,23,11,26,20进行信息投放时，能以最低的信息成本得到最大的信息覆盖率。
八、问题五的求解
8.1 信息传播模型的改进
图8.1信息传播示意图
影响端到端信息传播的因素既包括传播主体和传播客体的节点属性，也包括节点之间的通道关系。接下来，本文将基于附件1的通信数据和问题四的模型及结果，首先选择部分用户作为初始节点，抓取他们的主叫次数和被呼叫次数，然后采样他们所呼叫的对象的编号与通话时长。经过数据预处理后，最后的数据集 包 含 用 户 数 量36，连接关系10734，时 间 跨 度 从2016年09月01日—2016年12月31日。然后从多个维度提取信息传播的特征，包括节点属性特征和信息传播通道特征，针对节点间传播率进行综合建模，并找出显著影响因子。 8.2 信息传播各环节的特征 8.2.1节点特征 （1）传播主体特征Φs
节点影响力：节点影响力用该节点在一段时间内拨出的所有通话的影响力之和表示。
Influ (u )=lg (#RT +1) （8.1）
#RT 为该时段内一个节点平均呼叫对象数量。
节点权威度：用节点入度和出度的比值表示，在该通讯网络中，即一个用户的被呼叫次数与他主叫次数的比值：
⎛#followers ⎫
Auth (u )=lg （8.2）
+1⎪
⎝#friends ⎭
节点活跃度：用节点平均每天通话率表示。活跃度高的用户其传播的消息更容易被其用户接受并传播。
Act (u )=lg
⎛#posts ⎫
+1⎪ （8.3）
#days ⎝⎭
对于以上几个特征， 由于其所代表的物理意义不同， 在对数变换之后各个
特征取值范围不一， 需要进一步作标准化处理，本文采用Min-Max 标准化方法，将不同特征的取值映射到[0,1]区间：
x i -min {x j }max x j -min x j 1≤j ≤n
1≤j ≤n 1≤j ≤n
x =
'
i
（8.4）
其中x i 和x i ' 分别表示标准化处理前后的特征值。 （2）传播客体特征Φr
节点传播意愿：该特征用于度量用户接收到某条信息后是否愿意传播该消息。
用户一天中主叫次数与主叫次数和其被叫次数的比值表示其传播意愿，该值越大表示用户传播信息的主动性越强。
⎛#retweeted
Will (v )=lg
⎝#original posts ⎫
+1⎪ （8.6） posts ⎭
同样，该特征值经过Min-Max 标准化处理后, 取值范围为[0,1]区间。 8.2.2 边的特征
结构相似度：用两个节点的邻居集合的jaccard 距离表示其结构相似度：
Sim -s (u , v )=
N (u )⋂N (v )N u ⋃N v
（8.7）
其中, N (v i )表示v i 的邻居节点，通讯网络中两个用户的共同主叫对象和各自主叫对象的总和的比值。 联系亲密度：传播主体和传播客体是否分别是对方的朋友，与单向联系相比， 双向联系代表更强的关系：
⎧1, 若u, v 互相关注;
Follow (u , v )=⎨ （8.8）
⎩0，否则.
8.3模型求解
图4显示为端到端信息传播概率模型中各个特征的影响权重，该值经过了标准化处理。从图4可以看出，权重最大的特征是节点活跃度，其次是节点结构相似度以及节点权威度。
8.3.1 系数 8.4 结果分析
（1）节点活跃度
节点活跃度主要由通话率，即各个节点平均每天通话时间。通话时间越长，表明其在传播网络中存在时间越长，对传播率贡献越大。 （2）节点间结构相似度
在通讯网络中，如果两个节点之间的结构相似度较大， 即他们所认识的人群重合度较大，所谓“ 物以类聚， 人以群分”， 这通常表明二者具有共同的兴趣爱好， 或共同的社交圈子，这种潜在的强关系通常会促使更多的信息传播。 （3）信息主体的权威度
信息传播主体的权威度也是促使信息在网络中快速传播的重要因素, 一个可能的解释是随着通讯网络的发展，很多传统媒体、政府机构和社会组织越来越多地利用通讯平台发布最新的官方消息，由于这些用户权威度较大，消息一经发布便被快速传播从图4与图5可以很直观地看出，在影响信息传播的各种因素中， 节点用户的兴趣偏好、社会网络结构特点以及信息内容特征等等，都在信息传播过程中发挥着重要作用。 （4）是否相互通话
对于特征M (u , v )，表示双方是否互相通话，这大多发生在熟人圈子内，代表现实生活中已经存在的社会关系。该结果表明通讯网络中的信息传播受现实世界中真实社会关系的影响，使得信息熟人圈中传播，传播率反而小。 （5）信息的情感属性特征
另外一个有趣的发现是，虽然由于篇幅和未收集到准确，我们并没有建模分析信息的情感属性特征影响力，但经过文献查阅，发现负面情感特征的影响却大于正面情感特征，大概是正面信息：负面信息=1:3。这表明在通讯网络中上，负面消息比正面消息更容易吸引注意力，具有更强的传播能力，进一步对具体的信 息内容分析得知，负面情感特征较强的信息大多与某些紧急的、恶性的、恐慌的事件相关，比如自然灾害、交通事故、官场丑闻等等，这类事件相关的消息通常会以更快的速度在通讯网络中扩散。
九、模型的优缺点
9.1模型的优点
（1）针对问题一，本文运用了改进的K -MEANS 算法，以节点关联度为衡量指标进行分析，建立的模型更准确，所得结果也会更贴合实际。
（2）针对问题二，本文以社团结构划分算法基于相似度进行有向网络的节点
分群。成功构造模块度函数进行分群结果量化，从而更显著看出分群结果的优劣，并优化。
（3）针对问题三，运用MATLAB 绘制出个体间通信网络拓扑图，可以更清晰形象感知特征信息，从方面对数据进行解读，通过模型适用得到全面准确的个体分群结果。
（4）针对问题四，从数据中分析发现影响信息传播的因素，以此列为选择信息投入点的比较优先级，简化了许多搜索步骤，使问题解决更简便；此外，模型选择的消息获得率时50%，可以通过赋值改变，模型较为灵活。
（5）针对问题五，本文结合端到端信息传播概率模型，综合更多因素完善所建模型，并进行验证。 9.2模型的缺点
问题五中，由于没有准确数据，仅对传播主体、传播客体和传播路径特征对于信息传播率的影响进行分析和排序，缺少对传播内容的数据化分析。
十、模型改进
（1）考虑到现实网络中信息传播概率会随着传播时间间隔而演变：研究表明，节点之间的影响力或传播信息的能力随着时间间隔增大而衰减，符合指数衰减规律，因而在建立信息传播模型时，可以改变10-50%的信息传播终止率，改为动态衰减函数或用数组实现，下标越大，衰减的比例越大。
（2）随着在线社会网络的快速发展, 越来越多的人开始利用微博或Twitterd 等互联网平台来传播信息或分享观点，因而在问题五中，可以对收集在线社会网络中的信息传播相关数据，深入分析影响信息传播的可能因素，对于理解信息传播规律、预测信息传播态势、 进行互联网舆情监控具有重要意义。
十一、参考文献
[1] 周东浩 韩文报 王勇军 基于节点和信息特征的社会网络信息传播模型 解放军信息工程大学 2015年
[2] 刘恒，寇月, 申德荣，王泰明, 于戈 基于随机游走路径的分布式SimRank 算法 东北大学 2014年
[3] 于洋洋 基于并行聚类分析的社群发现算法研究 东北大学 2012年
[4] 徐丹丹 基于节点相似度的社团结构划分算法的研究 兰州理工大学 2016年
附录：
（1）问题二标准化模块度矩阵求特征值的matlab 程序 a=[1 1/sqrt(15) 1/sqrt(15) 1/sqrt(15) sqrt(3)/11; 1/sqrt(15) 1 2/5 2/5 sqrt(5)/11; 1/sqrt(15) 2/5 1 2/5 sqrt(5)/11; -1/sqrt(15) -1/5 -1/5 1 sqrt(5)/11;
-1/sqrt(33) -1/sqrt(55) -1/sqrt(55) sqrt(5)/11 1;]; eig(a)
（2）问题二广度优先搜索算法代码实现的源文件： //
// graph_bfs.cpp // 100-alg-tests //
// Created by bobkentt on 15-8-8.
// Copyright (c) 2015年 kedong. All rights reserved. //
#include #include #include #include #include
using namespace std; #define _DEBUG_ 1
void VertexNode::addEdge(Edge* _edge) { if (IsNull(_edge)) {
cout
#ifdef _DEBUG_
coutgetOri()->getKey(); coutgetDes()->getKey()
edgeAdj.push_back(_edge); return ; }
bool Graph::findNode(long key,VertexNode **_node) { list &VS = vertexSet;
list::iterator end = VS.end(); list::iterator it; VertexNode *node = NULL;
// 遍历顶点集，找到开始结点A
for (it = VS.begin(); it != end; it++) { node = *it;
if (node->getKey() == key)
{
break; } }
if (it == end) { // 结点中
cout
_node = NULL; return false; }
*_node = node; return true; }
VertexNode* Graph::addNode(long key,int value) { VertexNode * node = new VertexNode(key,value);
vertexSet.push_back(node);
return node; }
void Graph::addEdge(long keyOri,long keyDes,int weight) { VertexNode *ori = NULL; VertexNode *des = NULL; // 在图中查找这两个顶点
if (!findNode(keyOri, &ori) || !findNode(keyDes, &des)) { cout
// 创建此弧
Edge * edge = new Edge(weight,ori,des); // 在图中弧的起点的邻接表中，添加此弧 ori->addEdge(edge); return ; }
// 通过输入结点关键字_searchKey，找到该顶点 // 找到该顶点到图中其它可达顶点的最小距离
void Graph::bfs(long _searchKey,DistenceOfGraph& dis) { queue queueCache; int distence = 0;
// 若不存在此关键字，则返回 VertexNode *node = NULL;
if (!findNode(_searchKey, &node)) { return ;
}
// 查找点距离查找点的距离为0 node->setDistence(0);
node->setStatus(VISIT_NO_ADJ);
(dis).insert(pair(_searchKey,0)); // 广度优先遍历图
while (IsNotNull(node)) {
// 若顶点的邻接表已经被访问，则继续访问下一个顶点 if ( JudgeNodeStatusVisitAdj(node) ) { // queue next QueueNext(); continue; }
// 遍历顶点得全部临界顶点
Edge * edgeTmp = node->getEdgeHeader(); while (IsNotNull(edgeTmp)) { // 获取顶点的临接点
VertexNode * nodeTmp = edgeTmp->getDes();
// 若该顶点未访问过，则将此点加入队列，并设置到此点的距离 if (JudgeNodeStatusNoVisit(nodeTmp)) { queueCache.push(nodeTmp);
distence = edgeTmp->getOri()->getDistence() + edgeTmp->getWeight();
(dis).insert(pair(GetDesNodeKey((edgeTmp)),distence));
edgeTmp->getDes()->setDistence(distence); nodeTmp->setStatus(VISIT_NO_ADJ); }
EdgeNext(edgeTmp); }
QueueNext(); }
return; }
void Graph::printNode() {
list::iterator it = vertexSet.begin(); coutgetKey()
cout
int testGraphBfs() { Graph G;
// 画出图中所有的点
for (int i = 0; i
G.printNode();
// 画出图中所有的边
G.addEdge(1, 2, 1);/* V1-->V2 */ G.addEdge(1, 4, 1);/* V1-->V4 */ G.addEdge(2, 3, 1);/* V2-->V3 */ G.addEdge(3, 1, 1);/* V3-->V1 */ G.addEdge(4, 5, 1);/* V4-->V5 */ G.addEdge(5, 4, 1);/* V5-->V4 */
// 选择V3作为源点，求V3到其它所有的点的距离 DistenceOfGraph dis; G.bfs(3, dis);
// debug "for each dis"
map::iterator iter = dis.begin(); for (; iter != dis.end(); iter++) {
coutfirstsecond
return 0; }
int main(int argc, const char * argv[]) { testGraphBfs(); return 0; }
（3）问题三人物的编号表格：
（4）a=size(data,1);%对导入matlab 中数据求出大小 m=36;%设置节点个数 xx=rand(1,m);%生成节点
yy= rand(1,m);
str = [repmat(' ',m,1) num2str(n')];%对节点进行编号 mn=[xx;yy];
scatter(xx,yy); text(xx,yy,str);
for i=1:a%描绘网络连线
line([mn(1,data(i,3)),mn(1,data(i,5))],[mn(2,data(i,3)),mn(2,data(i,5))]) end
c=tabulate(data(:,3))%统计各成员个体主叫次数及及百分比 c
（5）问题三各成员主叫通话时长表格：
（6）问题三各成员拨打人数表格：
（8/** 创建数组 **/
array message_count = double(37); /** 拥有的消息数量 **/ array message_recv = double(37); /** 获得消息概率 **/
/** 初始化 设置初始通知的用户消息数为1 概率也直接为1**/ message_count[17]=1; message_recv[17]=1;
for (通话记录 order by time){
message_count[被叫] = message_count[被叫] + message_count[主叫]*0.1; /** message_count[i]最大值只能到1 **/
message_recv[被叫] = message_recv[被叫] + message_count[主叫]*0.1; /** message_count[i]最大值只能到1 **/ （9）问题5中显著性分析表
31