动态社交网络中基于电阻距离的动态演化社区发现系统及方法

动态社交网络中基于电阻距离的动态演化社区发现系统及方法

　　技术领域

　　本发明涉及社交网络研究领域，特别是涉及一种动态社交网络中基于电阻距离的动态演化社区发现系统及方法。

　　背景技术

　　近年来在线社交网络服务的日益流行，使用社交网络的用户数量呈现爆炸式增长。庞大的用户数量带来的不仅是更加复杂的网络结构，还有每时每刻都在产生的新的用户关系数据，例如微博网络中随时可能有新用户加入，而用户之间也随时可能会建立或者取消关注关系。这种会随着时间发生变化的社交网络被称为动态社交网络，动态社交网络是现实中社交网络更真实的展现，社区发现作为网络研究中的一个基础性问题，针对动态网络的社区发现能够挖掘动态社交网络中隐藏的规律与演化的趋势，对于分析和理解动态社交网络有着重要的作用。

　　在动态社交网络社区发现研究领域，大多数算法将动态网络划分为多个连续的时间片网络，发现每个时间片网络上的社区结构，然后对相邻时间片网络上的社区进行匹配，判断它们之间的关系并分析演化。在划分时间片上的社区结构时，针对动态网络中节点间的度量方式显得格外重要，因为节点间的距离决定了他们是否属于同一社区，而许多动态社区发现算法使用的一些传统距离度量没有考虑网络的时间性，很难准确反映节点间的稳定距离。并且在追踪社区的过程中，对于重要节点的发现有助于我们追踪社区轨迹。目前急需一种高精确度的算法以有效地处理此类问题。

　　发明内容

　　本发明目的是提供一种动态社交网络中基于电阻距离的动态演化社区发现系统及方法，以解决上述现有技术存在的问题，在保证算法准确度的前提下大幅度提高算法的时间效率。

　　为实现上述目的，本发明提供如下技术方案：

　　一种动态社交网络中基于电阻距离的动态演化社区发现系统，包括接收单元、数据预处理单元、计算单元、显示单元及主控单元；所述接收单元、数据预处理单元、计算单元、显示单元依次通过数据总线连接，主控单元分别和接收单元、数据预处理单元、计算单元、显示单元信号连接，接收单元、数据预处理单元、计算单元、显示单元再通过信号总线分别和主控单元连接；

　　所述接收单元用于接收动态社交网络数据并保存；

　　所述数据预处理单元用于将接收的社交网络数据编号并转换成具有T个时间片的网络序列G＝{G1,G2,...,GT}；

　　所述计算单元(4)的工作方式为：在各个时间片网络上基于节点间的电阻距离与共同邻居数量，计算节点之间的距离并通过节点与其邻居节点的距离与用户输入的参数α，为每个节点计算其局部亲密邻居阈值与局部最小聚类阈值，通过节点的局部亲密邻居数量与局部最小聚类阈值判断节点是否是核心节点，并通过核心节点传播社区成员身份，发现社区结构；通过计算社区距离，处理噪声社区，并计算节点动态贡献度，进行相邻时间片上的社区匹配，得到相邻时间片之间的社区演化事件；

　　所述显示单元用于将各个时间片网络上的社区结构与社区演化事件在屏幕上输出；

　　所述主控单元用于控制数据及信号在各单元间的流动顺序以及控制整个模型的运行。

　　优选地，所述动态社交网络数据用网络序列结构G＝{G1,G2,...,GT}，其中Gt＝(Vt,Et)表示在时间片t(1≤t≤T)时刻的网络结构，Gt是一个无向无权网络，Vt表示在Gt网络中节点集合，每个节点代表一个用户或者一个群组，Et表示在Gt网络中的边集，每条边代表两个节点之间的关系；保存了动态网络在各个时刻的拓扑结构。。

　　优选地，所定义的节点间的距离如下述公式：

　　

　　其中表示节点p和q在t时刻的距离，表示节点p在t时刻的邻居集合，表示在t时刻p节点与q节点之间的电阻距离，是t时刻p节点与邻居节点u的边的权重；

　　所定义的节点局部亲密邻居阈值如下述公式：

　　

　　其中表示节点p在t时刻邻居节点的数量；在t时刻，节点p的所有邻居中，若节点p与节点q的距离小于节点p的局部亲密邻居阈值或者小于节点q的局部亲密邻居阈值则节点q属于节点p的局部亲密邻居；节点的局部亲密邻居集合表示如下：

　　

　　所定义的局部最小聚类阈值其中α是用户输入的局部参数，根据α的大小可以调整社区结果中社区的形态；

　　所定义的社区距离如下述公式：

　　

　　其中CD(i，j)是噪声社区与他的掠夺区之间的距离，p与q是分别属于与的核心节点时刻的核心节点集合；

　　所定义的节点贡献度如下述公式：

　　

　　其中表示t时间片的i社区；所定义的节点动态贡献度为：

　　

　　优选地，所述主控单元的工作方式为：

　　在初始状态启动主控单元及显示单元后，接收单元接收社交网络数据，数据接收完毕后，接收单元通过信号总线向主控单元发出总线信号，主控单元启动数据预处理单元，通过信号总线向接收单元发出控制信号，接收单元通过数据总线向数据预处理单元传送数据，数据预处理单元接收数据并进行处理，数据处理完毕后通过信号总线向主控单元发出总线信号，主控单元接收总线信号并启动计算单元，主控单元向计算单元发出总线信号，计算单元开始计算，计算完毕后向主控单元发出总线信号，主控单元接收总线信号后启动显示单元，主控单元向计算单元发出信号，然后计算单元通过数据总线向显示单元传输数据，数据传输完毕后通过数据总线向主控单元发出总线信号，主控单元控制显示单元进行数据显示。

　　优选地，所述接收单元、数据预处理单元、计算单元、显示单元间的数据总线为单向数据总线，接收单元、数据预处理单元、计算单元、显示单元同主控单元间的信号总线为双向信号总线。

　　一种动态社交网络中基于电阻距离的动态演化社区发现方法，采用本发明动态社交网络中基于电阻距离的动态演化社区发现系统进行操作，包括如下操作步骤：

　　S1、通过接收单元获取动态社交网络数据，然后通过数据预处理单元将社交网络抽象成连续的时间片网络G＝{G1,G2,...,GT}，其中Gt＝(Vt,Et)表示在时间片t(1≤t≤T)时刻的网络结构，Gt是一个无向无权网络，Vt表示在Gt网络中节点集合，每个节点代表一个用户或者一个群组，Et表示在Gt网络中的边集，每条边代表两个节点之间的关系；

　　S2、输入最小聚类参数α与社区匹配参数β；

　　S3、将每个时间片建模成电阻网络，并根据电阻距离与共同邻居数量计算节点间的距离；

　　S4、根据节点间的距离与最小聚类参数α发现核心节点，并利用核心节点传播社区成员身份，构建基于核心节点搜索的社区发现模型，具体方法如下：

　　S41、定义节点的局部邻居阈值，节点p的局部邻居阈值为p与其所有邻居节点距离的几何平均值，与节点的距离小于最小聚类阈值的邻居为节点的局部亲密邻居；

　　S42、定义局部最小聚类阈值

　　S43、根据步骤S41所述的节点的局部邻居阈值和S42所述的局部最小聚类阈值发现核心节点，t时刻网络中的核心节点集合Coret表示如下：

　　S44、对于网络中的任一节点p，如果p是核心节点，则p与他的局部亲密邻居集合中的节点，形成一个以p为核心的社区如果两个核心节点是彼此的局部亲密邻居，则他们应该属于同一社区，故将他们各自所属的两个社区合并成一个社区；通过一系列的社区创建与社区合并发现社区结构；

　　S5、根据步骤S4得到的每个时间片上的社区序列C＝{C1,C2,...,CT}中，存在一些噪声社区，通过社区距离发现噪声社区的主社区并将噪声社区与其主社区合并；

　　S6、根据步骤S5得到的过滤噪声社区后的各时间片上的社区结构，计算每个节点在各个时间片网络上对其所在社区的重要性，与节点在不同时间片上对于社区重要性的稳定程度，即计算节点动态贡献度，根据节点动态贡献度将相邻时间片上的社区对进行匹配，根据匹配节点与社区规模发现社区在时间片间的演化事件，追踪社区结构。

　　优选地，所述步骤S3中的电阻距离为：网络中的边被视作是电阻，电阻值是边权重的倒数，在未加权网络中为1Ω，使用节点间的等价电阻作为节点对的电阻距离。

　　优选地，所述步骤S6中的社区匹配为：在相邻的两个时间片上的社区，当两个社区有相同的核心节点时对他们进行匹配计算；没有相同核心节点的社区不太可能跨时间片存在匹配关系。

　　本发明与现有技术相比较，具有如下显而易见的突出实质性特点和显著的技术进步：

　　1.本发明在对动态网络进行建模时考虑到了在动态网络中，由于网络的拓扑结构会发生改变，节点之间的距离随之变化，本发明准确的捕捉到了这种变化会对动态网络社区发现研究产生重要影响，同时考虑到了电阻距离由于综合了节点间的全部路径数量与路径长度之后可以得到较为稳定的节点距离，可保证其在动态网络中较为稳定，并基于节点之间的电阻距离发现网络中的核心节点；

　　2.本发明提出了一种基于核心节点发现的社区发现算法，以发现各个时间片网络上的社区结构，该模型由于利用电阻距离衡量节点距离而在动态网络中能提供稳定的距离度量，并且为每个节点计算局部阈值，可发现形态大小各异的社区；

　　3.本发明定义了噪声社区并利用社区距离进行了处理，提高了社区发现的质量，并定义了节点动态贡献度，能在动态网络中进行社区匹配时利用社区中的重要节点，更准确的发现社区演化事件，追踪社区演化。

　　附图说明

　　为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

　　图1为本发明改进的ECDR算法流程图。

　　图2为在真实网络上的模块度得分对比图。

　　图3为在真实网络上的NMI得分对比图。

　　图4为在DBLP数据集上运行本发明改进的ECDR算法发现的缩小事件在不同参数β下在各个时间片网络间的数量。

　　图5为在DBLP数据集上运行本发明改进的ECDR算法发现的增长事件在不同参数β下在各个时间片网络间的数量。

　　图6为在人工生成的动态网络BirthDeath网络上的模块度得分对比图。

　　图7为在人工生成的动态网络MergeSplit网络上的模块度得分对比图。

　　图8为在人工生成的动态网络ShrinkGrow网络上的模块度得分对比图。

　　图9为本发明动态社交网络中基于电阻距离的动态演化社区发现系统的结构框图。

　　具体实施方式

　　下面将结合本发明优选实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

　　为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本发明作进一步详细的说明。

　　实施例一：

　　参见图9，一种动态社交网络中基于电阻距离的动态演化社区发现系统，包括接收单元2、数据预处理单元3、计算单元4、显示单元5及主控单元1，所述接收单元2、数据预处理单元3、计算单元4、显示单元5依次通过数据总线连接，主控单元1和接收单元2、数据预处理单元3、计算单元4、显示单元5再通过信号总线分别和主控单元1连接；

　　所述接收单元2用于接收动态社交网络数据并保存；

　　所述数据预处理单元3用于将接收的社交网络数据编号并转换成具有T个时间片的网络序列G＝{G1,G2,...,GT}；

　　所述计算单元4的工作方式为：在各个时间片网络上基于节点间的电阻距离与共同邻居数量，计算节点之间的距离并通过节点与其邻居节点的距离与用户输入的参数α，为每个节点计算其局部亲密邻居阈值与局部最小聚类阈值，通过节点的局部亲密邻居数量与局部最小聚类阈值判断节点是否是核心节点，并通过核心节点传播社区成员身份，发现社区结构。通过计算社区距离，处理噪声社区，并计算节点动态贡献度，进行相邻时间片上的社区匹配，得到相邻时间片之间的社区演化事件；

　　所述显示单元5用于将各个时间片网络上的社区结构与社区演化事件在屏幕上输出；

　　所述主控单元1用于控制数据及信号在各单元间的流动顺序以及控制整个模型的运行。

　　实施例二：

　　本实施例与实施例一基本相同特别之处如下：

　　所述动态社交网络数据用网络序列结构G＝{G1,G2,...,GT}，其中Gt＝(Vt,Et)表示在时间片t(1≤t≤T)时刻的网络结构，Gt是一个无向无权网络，Vt表示在Gt网络中节点集合，每个节点代表一个用户或者一个群组，Et表示在Gt网络中的边集，每条边代表两个节点之间的关系；保存了动态网络在各个时刻的拓扑结构。

　　所定义的节点间的距离如下述公式：

　　

　　其中表示节点p和q在t时刻的距离，表示节点p在t时刻的邻居集合，表示在t时刻p节点与q节点之间的电阻距离，是t时刻p节点与邻居节点u的边的权重。

　　所定义的节点局部亲密邻居阈值如下述公式：

　　

　　其中表示节点p在t时刻邻居节点的数量；在t时刻，节点p的所有邻居中，若节点p与节点q的距离小于节点p的局部亲密邻居阈值或者小于节点q的局部亲密邻居阈值则节点q属于节点p的局部亲密邻居；节点的局部亲密邻居集合表示如下：

　　

　　所定义的局部最小聚类阈值其中α是用户输入的局部参数，根据α的大小可以调整社区结果中社区的形态。

　　所定义的社区距离如下述公式：

　　

　　其中CD(i，j)是噪声社区与他的掠夺区之间的距离，p与q是分别属于与的核心节点时刻的核心节点集合。

　　所定义的节点贡献度如下述公式：

　　

　　其中表示t时间片的i社区。所定义的节点动态贡献度为：

　　

　　所述主控单元1的工作方式为：在初始状态启动主控单元1及显示单元5后，接收单元2接收社交网络数据，数据接收完毕后，接收单元2通过信号总线向主控单元1发出总线信号，主控单元1启动数据预处理单元3，通过信号总线向接收单元2发出控制信号，接收单元2通过数据总线向数据预处理单元3传送数据，数据预处理单元3接收数据并进行处理，数据处理完毕后通过信号总线向主控单元1发出总线信号，主控单元1接收总线信号并启动计算单元4，主控单元1向计算单元4发出总线信号，计算单元4开始计算，计算完毕后向主控单元1发出总线信号，主控单元1接收总线信号后启动显示单元5，主控单元1向计算单元4发出信号，然后计算单元4通过数据总线向显示单元5传输数据，数据传输完毕后通过数据总线向主控单元1发出总线信号，主控单元1控制显示单元5进行数据显示。

　　所述接收单元2、数据预处理单元3、计算单元4、显示单元5间的数据总线为单向数据总线，接收单元2、数据预处理单元3、计算单元4、显示单元5同主控单元1间的信号总线为双向信号总线。

　　实施例三：

　　参见图1，本动态社交网络中基于电阻距离的动态演化社区发现方法，采用上述系统进行操作，其包括如下操作步骤：

　　S1、通过接收单元获取动态社交网络数据，然后通过数据预处理单元将社交网络抽象成连续的时间片网络G＝{G1,G2,...,GT}，其中Gt＝(Vt,Et)表示在时间片t(1≤t≤T)时刻的网络结构，Gt是一个无向无权网络，Vt表示在Gt网络中节点集合，每个节点代表一个用户或者一个群组，Et表示在Gt网络中的边集，每条边代表两个节点之间的关系。

　　S2、输入最小聚类参数α与社区匹配参数β；

　　S3、将每个时间片建模成电阻网络，并根据电阻距离与共同邻居数量计算节点间的距离；

　　S4、根据节点间的距离与最小聚类参数α发现核心节点，并利用核心节点传播社区成员身份，构建基于核心节点搜索的社区发现模型，具体方法如下：

　　S41、定义节点的局部邻居阈值，节点p的局部邻居阈值为p与其所有邻居节点距离的几何平均值，与节点的距离小于最小聚类阈值的邻居为节点的局部亲密邻居；

　　S42、定义局部最小聚类阈值

　　S43、根据步骤S41所述的节点的局部邻居阈值和S42所述的局部最小聚类阈值发现核心节点，t时刻网络中的核心节点集合Coret表示如下：

　　S44、对于网络中的任一节点p，如果p是核心节点，则p与他的局部亲密邻居集合中的节点，形成一个以p为核心的社区如果两个核心节点是彼此的局部亲密邻居，则他们应该属于同一社区，故将他们各自所属的两个社区合并成一个社区。通过一系列的社区创建与社区合并发现社区结构；

　　S5、根据步骤S4得到的每个时间片上的社区序列C＝{C1,C2,...,CT}中，存在一些噪声社区，通过社区距离发现噪声社区的主社区并将噪声社区与其主社区合并；

　　S6、根据步骤S5得到的过滤噪声社区后的各时间片上的社区结构，计算每个节点在各个时间片网络上对其所在社区的重要性，与节点在不同时间片上对于社区重要性的稳定程度，即计算节点动态贡献度，根据节点动态贡献度将相邻时间片上的社区对进行匹配，根据匹配节点与社区规模发现社区在时间片间的演化事件，追踪社区结构。

　　本实施例动态社交网络中基于电阻距离的动态演化社区发现方法以发现各个时间片网络上的社区结构，该模型由于利用电阻距离衡量节点距离而在动态网络中能提供稳定的距离度量，并且为每个节点计算局部阈值，可以发现形态大小各异的社区。本发明方法在保证算法准确度的前提下，大幅度提高算法的时间效率。

　　实施例四：

　　本实施例与实施例三基本相同，特别之处是：

　　所述步骤S3中的电阻距离为：网络中的边被视作是电阻，电阻值是边权重的倒数，在未加权网络中为1Ω，使用节点间的等价电阻作为节点对的电阻距离。

　　所述步骤S6中的社区匹配为：在相邻的两个时间片上的社区，当两个社区有相同的核心节点时对他们进行匹配计算。没有相同核心节点的社区不太可能跨时间片存在匹配关系。

　　实施例五：

　　参见图1-9所示，本动态社交网络中基于电阻距离的动态演化社区发现系统，针对现有的动态社区发现算法所存在的问题，提出改进的动态社区发现算法，可以获得更高的准确度，并通过实验作出验证。

　　本实施例中一个具有T个时间片的动态网络可以用一个网络序列G＝{G1,G2,...,GT}表示。令Gt＝(Vt,Et)表示在时间片t(1≤t≤T)时刻的网络结构，Gt是一个无向无权网络，Vt表示在Gt网络中节点集合，Et表示在Gt网络中的边集。

　　为了更全面的考虑节点间的通路数量以及路径长度对于节点间信息传播的影响，本实施例将时间片网络转换成电阻网络。网络中的边被视作是电阻，电阻值是边权重的倒数，在未加权网络中为1Ω，使用节点间的等价电阻作为节点对的电阻距离。计算各个时间片网络上节点对之间的电阻距离之后[5]，综合考虑邻居节点间的电阻距离与共同邻居，邻居节点间的距离度量方式如下：

　　

　　其中表示节点p和q在t时刻的距离，表示节点p在t时刻的邻居集合，表示在t时刻p节点与q节点之间的电阻距离，是t时刻p节点与邻居节点u的边的权重。本实施例使用每个节点的局部拓扑信息，自适应的为每个节点计算出局部亲密邻居阈值，根据节点的局部亲密邻居阈值，发现节点的局部亲密邻居。

　　在t时刻，节点p与其所有邻居节点距离的几何平均值，为节点p的局部亲密邻居阈值计算方式如下：

　　

　　其中表示节点p在t时刻邻居节点的数量；在t时刻，节点p的所有邻居中，若节点p与节点q的距离小于节点p的局部亲密邻居阈值或者小于节点q的局部亲密邻居阈值则节点q属于节点p的局部亲密邻居。

　　节点的局部亲密邻居集合表示如下：

　　

　　表示p节点在t时刻的局部亲密邻居集合，该集合中的节点与p节点的连接紧密程度超过网络中的其他节点，故可能与p同属一个社区。节点的局部亲密邻居集合中的节点越多，则代表越多的节点紧密连接在该节点周围，故该节点更有可能是社区中的重要节点。每个节点根据自己的局部信息，以及用户输入的局部参数α有自己的局部最小聚类阈值计算如下：

　　

　　其中是节点p的邻居数量，α是用户输入的局部参数，根据α的大小可以调整社区结果中社区的形态。通过节点的局部亲密邻居集合与局部最小聚类阈值，可以判断节点是否有资格成为核心节点。在t时刻，若节点p的局部亲密邻居数量不小于他的局部最小聚类阈值则节点p是一个核心节点。t时刻网络中的核心节点集合Coret表示如下：

　　

　　对于网络中的任一节点p，如果p是核心节点，则p与他的局部亲密邻居集合中的节点，形成一个以p为核心的社区如果两个核心节点是彼此的局部亲密邻居，则他们应该属于同一社区，故将他们各自所属的两个社区合并成一个社区。由于上述的核心节点特性，对于网络中的任一社区都有一个核心节点集合并且其中每个核心节点的局部亲密邻居集合中的所有核心节点都在中。这组核心节点通过一系列的社区创建与社区合并，将他们的局部亲密邻居与他们自己合并进同一个社区。

　　算法的伪代码详见如下。

　　

　　

　　在算法1中，首先初始化参数，Coret表示t时刻网络的核心节点集合,Ct表示t时刻网络的社区集合，k表示社区编号(line2)。之后将网络中的每个节点标记为未访问(unvisited)，并发现网络中的核心节点。遍历所有未访问节点，如果未访问节点p是核心节点，将创建一个新的社区，找出与核心节点p相连的核心节点连接集合，将集合中的节点与他们的局部亲密邻居集合中尚无社区所属的节点分配进该社区(line6-16)。如果遍历到的未访问节点p不是核心节点，则暂时将其标记为border(line18)。在搜索社区成员的过程中，标记为border的节点仍有可能获得社区成员的身份(line14)，但如果在遍历完所有节点之后仍有节点被标记为border，将这些节点标记为不属于任何社区的outlier(line19-20)。

　　通过算法1得到了每个时间片上的社区序列C＝{C1,C2,...,CT}，其中Ct表示t时间片上的社区集合。然而在这些社区结果中，可能会出现一些社区仅包含一两个节点，如此少的节点无法体现社区紧密连接的特性，所以是不合理的噪声社区，这样的噪声社区的存在降低了社区发现结果质量。噪声社区出现的原因是由于在非重叠社区中一个节点只能属于一个社区，但由于一个节点可能同时是多个节点的局部亲密邻居，故根据发现社区结构时遍历节点的顺序不同，一些核心节点的局部亲密邻居可能不会被划分进该节点所在社区。

　　若社区中，存在噪声社区中核心节点的局部亲密邻居，则是的掠夺区，噪声社区的掠夺区集合用表示。噪声社区的掠夺区社区中存在原属于该噪声社区的节点，掠夺区在削弱了噪声社区的社区性的同时，也是网络中与该噪声社区较为接近的社区。噪声社区与他的掠夺区之间的社区距离，为分属于他们的核心节点对的最小电阻距离，表示如下：

　　

　　其中CD(i，j)是噪声社区与他的掠夺区之间的距离，p与q是分别属于与的核心节点时刻的核心节点集合。在噪声节点的掠夺区集合中，与该噪声社区的社区距离最短的社区，为此噪声社区的主社区，噪声社区的主社区用表示。

　　噪声社区的主社区为网络结构中与其最为接近的社区，由于噪声社区已经不具有形成一个社区的资格，在噪声社区的掠夺区中找出与其社区距离最近的社区，将其作为该噪声社区的主社区。通过为每个噪声社区找到其主社区并与之合并，解决了输出结果集中噪声社区的问题。

　　通过基于电阻距离的社区发现算法，可以得到各个社区的核心节点集合，社区中的核心节点是社区中已知的重要节点。如果相邻时间片上的两个社区之间，没有任何一个相同的核心节点，则这两个社区不太可能存在演化关系，故不需要再对他们进行相似度计算。通过优先判断相邻时间片上社区对的核心节点重叠情况，可以减少许多不必要的社区相似度计算。

　　节点x在t时刻对于其所属社区的贡献度计算如下:

　　

　　节点贡献度体现了节点与社区内其他节点的连接紧密程度，节点贡献度越高，则表示该节点与社区内的其他节点的连接紧密程度越高，也代表其为社区整体的紧密连接做出了更大的贡献，这样的节点对于社区更加重要。然而在动态网络中，同一个节点在不同的时间片上，对于社区的贡献度可能会有变化，贡献度较稳定的节点，能为社区的紧密连接提供稳定的支持，所以更能标识一个社区。节点x在t时刻对于其所属社区的动态贡献度定义如下：

　　

　　在动态网络中，节点动态贡献度体现了节点对于其所属社区稳定的重要程度，节点动态贡献度更高的节点对于社区更重要。为了差异化的处理社区中的节点，在进行社区相似度计算时应该考虑节点的动态贡献度，最终相邻时间片上的两个社区与的相似度计算如下：

　　

　　其中表示和的相似度，越大则表示这两个社区越相似，若则与匹配成功，β是输入的参数，可以根据需要调整。对相邻时间片上有重叠核心节点的社区对进行上述的匹配过程，根据匹配情况与社区形态分析演化事件的发生。

　　7种社区演化事件的定义如下：

　　社区死亡：如果t时间片上的社区没有与t+1时间片上的任何社区匹配成功，则死亡。

　　社区诞生：如果t时间片上的社区没有与t-1时间片上的任何社区匹配成功，则诞生。

　　社区继续：如果与匹配成功并且则继续为这意味着虽然横跨两个时间片，但是这两个社区有着较高的相似度并且社区大小保持不变。

　　社区缩小：如果社区在时间片t+1上仅和成功匹配，并且则缩小为如果社区与时间片t+1上多个社区匹配成功，并且只有的大小小于则缩小为

　　社区增长：如果社区在时间片t+1上仅和成功匹配，并且则增长为如果社区与时间片t+1上多个社区匹配成功，并且只有的大小大于则增长为

　　社区分裂：如果社区与时间片t+1上的多个社区成功匹配，并且其中一个以上社区的规模小于则分裂为那些更小的社区。

　　社区合并：如果社区与时间片t上的多个社区成功匹配，并且其中一个以上社区的规模小于则那些较小的社区合并为

　　本实施例选择了五个静态真实网络数据集，DBLPCo-authorship与动态人工生成网络数据集。其中五个静态真实网络包括美国大学橄榄球网络，该网络有115个代表橄榄球队的节点，这些节点可以分为11个大社区和5个独立小组。该网络中有602条边，两个节点之间的边代表两个团队之间的比赛(NCAA)；海豚网络，这是一个由62个经常接触的海豚组成的无向无权网络，分为两个社区(DOLP)；Polbooks网络，该网络包含在亚马逊上出售的105本有关美国政治的书籍(POLB)；Zachary的空手道网络由34个代表空手道俱乐部成员的节点组成，78条边代表他们的关系，该网络中有两个社区，每个社区都有一个核心成员(KARA)；一个由241位医生组成的包含四个社区的合作网络(PHYS)。这五个真实网络已被广泛用于评估社交网络领域中算法的性能，并且每个都有基准社区结构。DBLPCo-authorship数据集是DBLP数据集的一个子集，其中有2753个节点代表作者，这个网络是这些作者从1990年到2010年合作发表文章的关系网络，每一条存在的边代表两个作者在1990到2010间曾合作发表过论文。这个动态网络按照时间被分为9个时间片并且没有基准社区结构。本实施例使用扩展的LFR生成器生成的三个网络(N＝15000,k＝20,kmax＝40,Cmin＝20,Cmax＝60,τ1＝-2,τ2＝-1,μ＝0.2,On＝0,Om＝1)。这些网络包括BirthDeath，其中诞生和死亡事件将在相邻的时间片之间发生；MergeSplit，其中合并和分裂事件将在相邻时间片之间发生；ShrinkGrow，其中收缩和增长事件将在相邻的时间片之间发生。每个动态网络有10个时间片和15,000个节点。

　　本实施例算法实验中，在数据预处理部分对实验使用的部分进行了简单的整理。实验主要部分使用了本实施例提出的基于电阻距离的动态演化社区发现ECDR(Evolutionary Community Discovery via Resistance distance)算法进行对比试验。

　　为了验证本实施例所提算法的有效性，本实施例使用五个静态真实网络数据集，DBLP Co-authorship与动态人工生成网络数据集。并选择了该研究领域COPRA，SHRINK，SLAP算法作为比较的基准，应该注意的是，就作者所知，现今没有公认比较好的方法能够衡量社区演化事件发现结果的质量，因此对于社区发现结果，在本实施例中提供了各个网络上本实施例提出的算法与其他算法的社区发现结果比较，而对于社区演化事件，仅给出了ECDR的演化事件发现结果用于演化分析。

　　如图2所示，与其他方法相比，ECDR获得了更高的模块度得分，甚至在DOLP，KARA和POLI上的模块度为1。图3显示，在大多数数据集上ECDR也获得出色的NMI得分，并在DOLP上获得了满分。在具有由管理员和俱乐部教练组成的两个社区的KARA网络中，所提出的ECDR算法可以确定该网络中的两个社区，并将代表管理员和教练的节点标识为核心节点。参数α的值会显著影响结果，较低的α值意味着网络中的节点易于成为核心节点，核心节点的数量增加使社区成员资格更易于传播，并趋于形成松散连接的大型社区。高的α值意味着节点难以核心节点，因此最终得到的社区结构中社区内部往往连接密度较高。但是，α的值若太高将导致成为核心节点的条件过于苛刻，网络中极少节点可以成为核心节点，社区成员资格难以相互传播以至于网络中很多节点甚至没有社区所属。α值可以根据社区密度的要求进行调整，在这项工作中，建议的α值是在实验中使用的[0.4；0.6]范围内。在这样的范围内，可以识别与邻居节点紧密连接的核心节点，而不仅仅是具有较大节点度的节点。

　　参数β是演化分析中非常重要的参数，他控制着演化结果的准确性。图4与图5展示了DBLP数据集中随着参数β的变化，缩小与增长事件数量的变化情况，可以很明显的看到，随着β值的增加演化事件的数量随之减少，这是因为β的取值体现了对于噪声的容忍程度。β取值越小社区对越容易匹配成功，如果取值过小会导致很多匹配成功的社区对相似度很低，虽然增加了演化事件的数量但是减少了准确度。而β的取值如果过大会让原本相似的社区无法匹配成功。从图中可以看出当β取0.3-0.7的时候事件的数量比较稳定。其他的事件也展现了相同的倾向，除了死亡与诞生事件。死亡事件的数量会随着β值的增加而增加，因为随着β的增加，t时刻的社区越难与t+1时刻的社区匹配成功，当β取值为1，除了完全不变的社区，所有t时刻的社区都会被判定为死亡。诞生事件随β变化的趋势与死亡事件相同。

　　图6至图8显示了在三个人工合成动态网络上各种方法获得的社区结构的模块度评分。可以看出，ECDR的性能要优于其他方法，因为即使是在最难识别的BirthDeath网络中，ECDR方法也获得了最高的模块度得分，并且在十个时间片中保持稳定。

　　同时，本实施例还提供了一种动态社交网络中基于电阻距离的动态演化社区发现计算模型，如图7所示，此计算模型包括接收单元、数据预处理单元、计算单元、显示单元、总控单元。

　　数据获取单元用于接收动态社交网络数据并保存。

　　所述数据预处理单元用于将接收的社交网络数据编号并转换成具有T个时间片的网络序列G＝{G1，G2，...,GT}；

　　所述计算单元的工作方式为：在各个时间片网络上基于节点间的电阻距离与共同邻居数量，计算节点之间的距离，并通过节点与其邻居节点的距离与用户输入的参数α，为每个节点计算其局部亲密邻居阈值与局部最小聚类阈值，通过节点的局部亲密邻居数量与局部最小聚类阈值判断节点是否是核心节点，并通过核心节点传播社区成员身份，发现社区结构。通过计算社区距离，处理噪声社区，并计算节点动态贡献度，进行相邻时间片上的社区匹配，得到相邻时间片之间的社区演化事件；

　　输出单元的功能是将各个时间片网络上的社区结构与社区演化事件在屏幕上输出；

　　实验证明，本实施例的ECDR算法作为改进的动态社区发现算法，社区发现的准确度要高于一般的社区发现算法，并且能够在动态网络中发现社区演化事件，追踪社区演化轨迹，从而能够将本实施例中的ECDR算法用于解决现实生活中发现动态演化社区的问题。

　　在本发明的描述中，需要理解的是，术语“纵向”、“横向”、“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明，而不是指示或暗示所指的模型或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制。

　　以上所述的实施例仅是对本发明的优选方式进行描述，并非对本发明的范围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。