本发明涉及复杂网络领域，具体涉及一种基于网络结构和节点内容的重叠社区演化分析方法及系统。
背景技术：
现实生活中许多系统都可以用一张复杂社会网络的抽象图表示，在这些网络结构图中，每个个体用一个节点表示，节点间的边表示个体之间的联系。通过对网络结构图的分析可以帮助了解网络拓扑结构，进一步发掘复杂网络中隐藏规律，对基于复杂网络的预测、推荐等具有重要意义。
为了挖掘网络中的社区结构，业界也已提出不少社区发现方法，这些方法大多是基于网络结构进行社区发现，忽略了节点的内容属性，社区缺乏语义性；也有少数算法利用网络中节点的内容属性进行挖掘社区，但这类方法又常常忽略了网络结构属性，导致挖掘到的社区存在不少问题。并且传统社区发现算法计算复杂度相对较高，难以应对高维稀疏的复杂网络，而基于网络中节点内容建模的社区发现方法很少考虑到节点文本内容短小情况下的数据稀疏问题。因此，为能够充分考虑复杂网络的拓扑结构和网络中节点的文本内容属性，本发明方法将机器学习中网络表示学习算法和主题模型建模思想融合到社区发现中，以便更好的挖掘复杂网络中的社区结构以及更好揭示社区内部特征和潜在规律。
技术实现要素：
本发明的目的在于提供一种基于网络结构和节点内容的重叠社区演化分析方法及系统，有效解决复杂网络中重叠社区归属分布问题。
实现本发明目的的技术方案是：
一种基于网络结构和节点内容的重叠社区演化分析方法，包括以下步骤：
步骤1、基于网络拓扑结构，生成网络中每个节点的社区聚类结果，然后得到基于节点结构的社区发现结果；
步骤2、基于每个节点内容属性值和步骤1的社区发现结果，生成网络中节点随时间点变化的重叠社区归属分布概率矩阵模型，进而得到每个节点的重叠社区归属分布。
进一步的，所述步骤1具体为：
步骤1-1、根据网络图中节点的结构关系提取节点的邻接矩阵；
步骤1-2、将节点的邻接矩阵作为输入通过节点向量表示算法进行训练，得到节点的低维向量表示矩阵；
步骤1-3、对节点的低维向量表示矩阵进行数据处理，得到聚类样本数据；
步骤1-4、聚类样本数据作为输入，采用聚类算法进行建模，得到节点聚类结果；
步骤1-5、分析网络中节点的聚类结果，最终得到基于节点结构的社区发现结果。
进一步的，所述步骤1-2中节点向量表示算法采用deepwalk模型进行训练，得到的节点低维向量表示矩阵需能够反应节点在原网络中的结构关系。
进一步的，所述步骤1-4中聚类算法采用变分贝叶斯高斯混合模型自动计算聚类结果中类的个数。
进一步的，所述步骤2具体为：
步骤2-1、根据复杂网络中节点的内容关系构建节点的内容属性值；
步骤2-2、对节点的内容属性值进行分词处理，得到标准内容属性值，即下一步模型的标准数据输入格式；
步骤2-3、将标准内容属性值作为输入，构建模型，得到节点的重叠社区归属分布概率矩阵模型；
步骤2-4、分析节点的重叠社区归属分布概率矩阵模型，得到节点的社区归属结果。
进一步的，所述步骤2-2中分词处理包括去除数字、标点符号和停用词。
进一步的，所述步骤2-3构建模型包括：
基于lda主题模型建模，生成重叠社区归属分布概率模型；
采用collapsedgibbssampling方法对生成的模型推理，得到重叠社区归属分布概率模型的采样模型；
对采样模型进行训练，得到收敛的重叠社区归属分布概率模型。
进一步的，所述基于lda主题模型建模时引入spikeandslabprior方法和时间片方法。
进一步的，所述重叠社区归属分布概率模型的采样模型为：
其中，θm,c,t为第t时社区概率分布矩阵模型，
一种基于网络结构和节点内容的重叠社区演化分析系统，包括社区发现模块和重叠社区动态演化分析模块；其中：
所述社区发现模块基于网络拓扑结构，用于生成网络中每个节点的社区聚类结果，然后得到基于节点结构的社区发现结果；
所述重叠社区动态演化分析模块基于节点内容属性值和社区发现模块的社区发现结果，用于生成网络中每个节点随时间点变化的重叠社区归属分布概率矩阵，得到每个节点的重叠社区归属分布。
与现有技术相比，本发明具有如下有益效果：
(1)本发明技术提出了一种新的社区发现方法，综合考虑网络中节点结构关系和节点文本内容属性值，将二者有机结合在一起，能够更加有效的对社区进行划分；
(2)传统的社区发现方法难以解决高维稀疏的复杂网络，并且计算复杂度高，而本方法首先采用网络表示学习算法将复杂网络中节点表示成低维向量，然后再对低维向量进行聚类，有效降低了计算复杂度；
(3)针对复杂网络中节点的内容属性为短文本情况，将spikeandslabprior方法融入到主题模型，有效解决数据稀疏问题；
(4)复杂网络中节点所属社区可能随时间变化产生改变，而传统社区发现方法很难发现社区的动态演变特性，本发明方法则将时间片思想融合到主题模型中，能够挖掘出网络中节点的社区演变；
(5)传统的重叠社区发现算法通常计算的是节点处于各个重叠社区的明确结果，一方面重叠节点较少，另外一方面重叠节点归属的社区数目存在限制，而本发明方法则得到的是节点在重叠社区上的归属分布概率，有效解决了上述两个问题。
下面结合附图对本发明作进一步详细的说明。
附图说明
图1为本法发明方法的流程示意图。
图2为基于网络拓扑结构进行社区发现算法具体流程图。
图3为基于节点内容属性值进行重叠社区动态演化分析方法流程图。
图4为节点内容属性值建模算法具体流程图。
具体实施方式
结合图1，本发明提出了一种基于网络结构和节点内容的重叠社区演化分析方法，包括以下步骤：
步骤1、基于网络拓扑结构，生成网络中每个节点的社区聚类结果，然后得到基于节点结构的社区发现结果；
步骤2、基于节点内容属性值和步骤1的社区发现结果，生成网络中每个节点随时间点变化的重叠社区归属分布概率矩阵，进而得到节点的社区归属结果。
步骤1的社区发现结果和步骤2的社区归属结果用于社区挖掘结果分析。
结合图2所示，所述步骤1包括如下步骤：
步骤1-1、首先根据复杂网络中节点的结构关系构建网络节点的邻接矩阵；
步骤1-2、将节点的邻接矩阵作为输入通过节点向量表示算法进行训练，得到节点的低维向量表示矩阵，向量与向量之间的关系可以反应节点在网络中结构关系；
步骤1-3、将节点的低维向量表示矩阵进行数据处理，得到下一步聚类模型的标准数据输入格式，即聚类样本数据；
步骤1-4、将处理后的节点向量矩阵输入到变分贝叶斯高斯混合模型中进行训练，得到网络中每个节点的聚类结果；
步骤1-5、对聚类结果分析，得到社区归属结果即为在网络中所属的社区。
其中，步骤1-2中节点向量表示算法采用deepwalk网络表示学习算法，如下表：
在上表中，g表示网络图，v表示网络图g中节点的集合，e则为g中节点边的集合，ο表示随机排序后的节点集合，w、d、t则为deepwalk网络表示学习算法中所用到的参数，w表示滑动窗口大小，d表示向量维度大小，t表示随机游走序列长度，φ则为节点向量表示矩阵，vi表示v中第i个节点，t表示时间，wvi表示随机游走序列。从表中算法过程可知，节点向量表示算法的过程包括随机游走和不断迭代更新两部分。随机游走生成器随机选取网络中各节点，生成以这些节点为根的随机游走序列，且每个节点生成的游走序列长度和个数均相同。在每一轮迭代更新过程中，将随机游走序列和节点表示矩阵φ输入到skipgram算法中，更新节点的向量表示矩阵φ，直至循环结束，最终生成低维向量表示矩阵φ。
所述步骤1-4具体流程如下表：
变分贝叶斯混合高斯模型聚类首先对模型参数初始化，然后对模型参数进行推断计算，不断迭代更新，直至达到最大循环次数，最终得到每个节点的簇划分，即为所属的社区。
结合图3所示，所述步骤2包括如下步骤：
步骤2-1、根据复杂网络中节点的内容关系构建节点的内容属性值；
步骤2-2、对节点的内容属性值进行分词处理，去除数字、标点符号、停用词等等，得到标准主题模型数据输入格式，减少无用数据词汇，进一步提高算法建模精确性；将文本主题模型应用与社区发现中，网络中每个节点对应主题模型中的每篇文档，节点社区对应主题模型中的主题，节点重叠社区归属分布对应主题模型中文档在各个主题中的分布情况，每个社区中分布的关键内容属性值对应主题模型中每个主题的高频词；
步骤2-3、对lda主题模型进行改进，引入spikeandslabprior方法解决节点内容短小造成的数据稀疏问题，同时结合时间片方法解决节点内容属性值随时间变化造成的重叠动态归属分布问题，从而最终得到节点的重叠社区归属分布概率矩阵模型；
步骤2-4、对节点的重叠社区归属分布概率矩阵模型进行分析，发现节点所归属的几个主要社区，这些社区即为重叠社区，进一步分析可发现，节点在每个重叠社区的归属概率应有所不同，即重叠社区之间也有主次之分。
通过对每个节点携带的内容属性值进行建模，得到节点上的社区归属概率分布矩阵模型，通过分析概率分布矩阵模型，最终可获知每个节点上的重叠社区归属分布。
结合图4所示，所述社区归属概率分布矩阵模型中设计到的符号参数定义说明如下表：
该模型是基于lda主题模型的改进，主要对多项式分布θ和
社区归属概率分布矩阵模型生成过程是模拟网络中每个节点携带内容属性值的生成过程，用多项式分布θ模拟节点上的社区分布，用多项式分布
下表所列为该模型的生成过程：
模型推理过程采用collapsedgibbssampling方法进行推理上述算法中的参数，该算法为本领域公知算法，本发明此处对推理细节不详细阐述，下面给出主要使用的采样公式。
节点所属社区c的采样公式如下：
其中，
πm和bm的联合条件分布采样公式：
其中，bm表示节点m中的社区集合，am表示社区选择器b为1的集合，
第t时社区多项式分布模型θm,c,t和词多项式分布模型
其中，θm,c,t为第t个采样时刻社区概率分布矩阵模型，
得到采样模型，即可基于网络节点训练集进行训练，通过训练得到的模型进行社区语义分析。下表中所列即为采样模型训练流程：
上述模型训练结束后，可得到两个矩阵，分别为社区-词概率分布矩阵模型
基于上述重叠社区演化分析方法，一种基于网络结构和节点内容的重叠社区演化分析系统，包括基于网络拓扑结构进行社区发现模块和基于节点内容属性值进行重叠社区动态演化分析模块；
所述基于网络拓扑结构进行社区发现模块，用于生成网络中每个节点的社区聚类结果；
所述基于节点内容属性值进行重叠社区动态演化分析模块，用于产生网络中每个节点随时间点变化的重叠社区归属分布概率矩阵，能够得到节点在主要社区上的归属结果，进而更好的挖掘复杂网络中节点的内在特征和潜在的规律。
关于重叠社区演化分析系统各模块的具体限定可以参见上文中对于演化分析方法的限定，在此不再赘述。
1.一种基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，包括以下步骤：
步骤1、基于网络拓扑结构，生成网络中每个节点的社区聚类结果，然后得到基于节点结构的社区发现结果；
步骤2、基于每个节点内容属性值和步骤1的社区发现结果，生成网络中节点随时间点变化的重叠社区归属分布概率矩阵模型，进而得到每个节点的重叠社区归属分布。
2.根据权利要求1所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤1具体为：
步骤1-1、根据网络图中节点的结构关系提取节点的邻接矩阵；
步骤1-2、将节点的邻接矩阵作为输入通过节点向量表示算法进行训练，得到节点的低维向量表示矩阵；
步骤1-3、对节点的低维向量表示矩阵进行数据处理，得到聚类样本数据；
步骤1-4、聚类样本数据作为输入，采用聚类算法建模，得到节点聚类结果；
步骤1-5、分析网络中节点的聚类结果，最终得到基于节点结构的社区发现结果。
3.根据权利要求2所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤1-2中节点向量表示算法采用deepwalk模型。
4.根据权利要求2所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤1-4中聚类算法采用变分贝叶斯高斯混合模型。
5.根据权利要求1所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤2具体为：
步骤2-1、根据复杂网络中节点的内容关系构建节点的内容属性值；
步骤2-2、对节点的内容属性值进行分词处理，得到标准内容属性值，即下一步模型的标准数据输入格式；
步骤2-3、将标准内容属性值作为输入，构建模型，得到节点的重叠社区归属分布概率矩阵模型；
步骤2-4、分析节点的重叠社区归属分布概率矩阵模型，得到节点的社区归属结果。
6.根据权利要求5所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤2-2中分词处理包括去除数字、标点符号和停用词。
7.根据权利要求5所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述步骤2-3构建模型包括：
基于lda主题模型建模，生成重叠社区归属分布概率模型；
采用collapsedgibbssampling方法对生成的模型推理，得到重叠社区归属分布概率模型的采样模型；
对采样模型进行训练，得到收敛的重叠社区归属分布概率模型。
8.根据权利要求7所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述基于lda主题模型建模时引入spikeandslabprior方法和时间片方法。
9.根据权利要求7所述的基于网络结构和节点内容的重叠社区演化分析方法，其特征在于，所述重叠社区归属分布概率模型的采样模型为：
其中，θm,c,t为第t时社区概率分布矩阵模型，
10.一种基于网络结构和节点内容的重叠社区演化分析系统，其特征在于，包括社区发现模块和重叠社区动态演化分析模块；其中：
所述社区发现模块基于网络拓扑结构，用于生成网络中每个节点的社区聚类结果，然后得到基于节点结构的社区发现结果；
所述重叠社区动态演化分析模块基于节点内容属性值和社区发现模块的社区发现结果，用于生成网络中每个节点随时间点变化的重叠社区归属分布概率矩阵，得到每个节点的重叠社区归属分布。
技术总结