计算机设计大赛炫酷展示

1、背景与意义背景与意义功能介绍功能介绍技术知识技术知识创新之处创新之处1234未来展望未来展望5 社会网络（social network）是由图表示的异构多关系数据集，图中节点对应对象，边对应表示对象间联系或相互作用的链接。过去的几十年间，社会网络受到越来越多的关注。特别是移动网络和互联网的发展，产生了大量的，容易被计算机处理的社会网络数据。从这些数据中获取知识，从而理解商业行为，识别业务模式，捕捉用户行为，更好利用资源，提高服务质量，将成为运营商的核心竞争力之一。 对于现在大数据的时代中，挖掘出社交网络上的社区很有实用价值。社区内用户的共同话题，会形成一个定向的区别用户的方式，为智能搜索、个性

2、化服务、商业应用推广等应用提供理论依据。从广告投放的角度来看，容易找到定向的广告受众; 从朋友推荐的角度看，能够方便的将同一个社区内的个体向其他个体进行推荐，为找寻多年没有联系的朋友提供一个方便快捷的途径。 将社会网络分析以一种数据可视化的形式展示给决策者，不仅能形象直观，还有助于其在庞大的数据中能及时捕获所需信息。数据可视化，是关于数据之视觉表现形式的研究。如今，可视化已经不仅仅是点和线的简单描绘，它成为了一种能传递深层数据内涵、启发问题解决方案的强大智能模型。 类似这样的软件，在国外著名的有UCINET、Pajek以及Gephi等，UCINET、Pajek侧重于社会网络的分析，但可视化的效

3、果较差，而且操作不简单，忽略用户体验；Gephi是则偏向于社交图谱的数据可视化，能生成漂亮的可视化图形，并对数据进行清洗和分类，但数据分析不够全面，提供算法较少。另外，这些软件都需用户下载才能使用，不支持web端，这样导致电脑因系统的差异而使用不了某些软件，如Gephi需jdk1.7以下的环境配置，不支持jdk1.8。 针对上述的不足，我们小组研发了一个基于web端的社会网络可视化分析平台，名为vina，力求将社会网络分析与数据可视化充分结合，以给用户更好的体验效果。 项目简介： 本系统是一个基于开源框架Django的社会网络可视化分析网站，并且尽可能简单灵活地使数据可视化。特点是UI美观、使

4、用简单、支持大多数浏览器、支持多种文件格式的输入、提供多种社区划分算法。数据可视化的结果包括了网络图、柱状图、饼图、表格，让用户从不同角度获得社区网络划分的结果。另外，本系统还运用了社会网络分析的知识，为用户挖掘出网络中的重要信息。本系统的用途可分为：客户群体细分、社交网络分析、热点事件分析、舆情监控、社会网络划分的教学等。 支持多种文件格式的输入提供多种社区划分算法UI美观使用简单基于web项目特点： 项目用途： 登陆网站，登陆网站，注册登录注册登录 导入文件，导入文件，选择算法选择算法 得到输出，得到输出，分析结果分析结果退出登录退出登录系统使用流程：本系统的网址为http：/120.25

5、.203.152:8000文件导入格式： 我们导入的文件有两个，第一个是网络信息文件，文件的内容以source，target，weight为格式，source代表源点，target代表目标点，weight代表连边权重，例如节点1对节点6有连边，连边权重为2，我们记录的格式为“1,6,2”。 第二个是节点标签文件，文件的内容是节点所对应的标签，以node，label为格式，例如节点1的标签叫quincy。 两份文件均支持txt，xls和csv格式 网络信息文件：网络信息文件：标签文件标签文件LPABGLL WALK-TRAPFAST-GREEDY WorldCannotReceiveWorldC

6、annotSeeWorld doesNot KnowWillDwell inDisciples社区划分算法社区划分算法四种算法都具有良好的社区划分效果，四种算法都具有良好的社区划分效果，不同的算法适用于不同的场景不同的算法适用于不同的场景LPA：快速高效：快速高效 BGLL：稳定准确稳定准确 Walktrap：划分效果好：划分效果好 Fastgreedy： 适用大型加适用大型加权网络权网络 算法特点：算法特点：1、label propagation Algorithm(LPA) 标签传播算法（标签传播算法（LPALPA）是由）是由ZhuZhu等人于等人于20022002年提出，它是一种基于图的

7、半年提出，它是一种基于图的半监督学习方法该算法的基本原理如下：首先，给全网每个节点分配一个不重监督学习方法该算法的基本原理如下：首先，给全网每个节点分配一个不重复的标签（复的标签（labellabel）；其次，在迭代的每一步，让一个节点采用在它所有的）；其次，在迭代的每一步，让一个节点采用在它所有的邻居节点中最流行的标签（如果最佳候选标签超过一个，则在其中随机抽一邻居节点中最流行的标签（如果最佳候选标签超过一个，则在其中随机抽一个），；最后，在迭代收敛时，采用同一种标签的节点被归入同一个社区。个），；最后，在迭代收敛时，采用同一种标签的节点被归入同一个社区。 这个算法的核心是通过标签的扩散来模

8、拟某种流在网络上的扩散。其优势是这个算法的核心是通过标签的扩散来模拟某种流在网络上的扩散。其优势是算法简单，特别适用于分析被流所塑造的网络。在大多数情况下可以快速收算法简单，特别适用于分析被流所塑造的网络。在大多数情况下可以快速收敛。其缺陷是，迭代的结果有可能不稳定，尤其在不考虑连边的权重时，如敛。其缺陷是，迭代的结果有可能不稳定，尤其在不考虑连边的权重时，如果社区结构不明显，或者网络比较小时，有可能所有的节点都被归入同一个果社区结构不明显，或者网络比较小时，有可能所有的节点都被归入同一个社区。社区。 Reference:Raghavan, U.N. and Albert, R. and Ku

9、mara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E76:036106, 2007. /abs/0709.2938 .技术知识技术知识2、BGLL 这个方法分两步：这个方法分两步：（1 1）从节点合并开始，）从节点合并开始， 构建第一步社团划分结果。每个节点根据模块度增构建第一步社团划分结果。每个节点根据模块度增益决定是否加入到邻居节点的社团中和到底加入到哪个邻居节点的社团中。益决定是否加入到邻居节点的社团中和到底

10、加入到哪个邻居节点的社团中。每个节点按序执行该过程。每个节点按序执行该过程。（2 2）重新构建网络。把第一步每个社团单做一个节点，边是原来社团之间）重新构建网络。把第一步每个社团单做一个节点，边是原来社团之间链接边权的和。链接边权的和。（3 3）迭代（迭代（1 1），（），（2 2），直到收敛。），直到收敛。 Reference: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks. J Stat Mech P10008(

11、2008), /abs/0803.04763、Walktrap 算法的初始条件为每个结点为一个单独的社区，然后逐步合并可使结点和算法的初始条件为每个结点为一个单独的社区，然后逐步合并可使结点和它所在社区之间的平方距离均值达到最小的两个社区。每一步都要更新社区它所在社区之间的平方距离均值达到最小的两个社区。每一步都要更新社区之间的距离，其中两个结点之间的距离对应于它们的相似度，即在一个离散之间的距离，其中两个结点之间的距离对应于它们的相似度，即在一个离散的随机游走过程中，它们之间的方向转移概率。的随机游走过程中，它们之间的方向转移概率。 Reference: Pas

12、cal Pons, Matthieu Latapy: Computing communities in large networks using random walks, /abs/physics/0512106 4、Fastgreedy 一种基于贪婪法思想的凝聚算法，并称这种算法为快速算法。将网络划分一种基于贪婪法思想的凝聚算法，并称这种算法为快速算法。将网络划分为为K K个社团，定义一个个社团，定义一个k k* *k k维的对称矩阵维的对称矩阵E=E=（），其中元素，表示网络连接两（），其中元素，表示网络连接两个不同社团的节点的边在所有边中占的比例；这两个节

13、点分别位于第个不同社团的节点的边在所有边中占的比例；这两个节点分别位于第i i个社个社区和第区和第j j个社区。个社区。1.1.初始化网络为初始化网络为N N个社团，即每个节点就是一个独立社团。个社团，即每个节点就是一个独立社团。2.2.依次合并有边相连的社团对，并计算合并后的模块度增量，根据贪婪算法依次合并有边相连的社团对，并计算合并后的模块度增量，根据贪婪算法的原理，每次合并应该沿着模块度增大最多或者减少最少的方向进行。每次的原理，每次合并应该沿着模块度增大最多或者减少最少的方向进行。每次合并以后，对对应的元素更新，并将与合并以后，对对应的元素更新，并将与i i、j j社团相关的行和列相加

14、。社团相关的行和列相加。3.3.重复步骤重复步骤2 2，不断合并社团，直到整个网络都合并为一个社团。，不断合并社团，直到整个网络都合并为一个社团。4.4.整个算法完成后，得到一个社区结构分解的树状图。再通过选择在不同位整个算法完成后，得到一个社区结构分解的树状图。再通过选择在不同位置断开可以得到不同的网络社区结构。在这些社区结构中，选择一个对应局置断开可以得到不同的网络社区结构。在这些社区结构中，选择一个对应局部最大模块度值的结构，就得到最好的网络社区结构。部最大模块度值的结构，就得到最好的网络社区结构。 Reference: A. Clauset, M. E. J. Newman and C

15、. Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).社区划分 通过社区划分算法将一个网络划分成不同社区，同一个社区的节点联系较为紧密，不同社区的节点联系较为稀疏。效果如下： 社会网络分析社区结构分析核心人物挖掘好友推荐核心人物挖掘：中心性分析： 描述图中任何一点在网络中占据的核心性源于社会计量学的”明星“概念，一个核心点是那种处于一系列关系核心的位置，即该点与其他点有众多的直接联系。若某点具有最高点度中心度，则称该点居于中心。 我们通过点度中心度挖掘出网络中核心人物，

16、而点度中心度可分为绝度中心度和相对中心度。一般采用相对中心度较为准确。社区结构分析：社区结构分析：1.1.社区密度：社区密度： 反映社区内的紧密程度，密度值反映社区内的紧密程度，密度值0 0到到1 1之间，越接近之间，越接近1 1则代表彼此关系越则代表彼此关系越紧密。紧密。 一般将密度定义为一般将密度定义为“图中实际存在的线的条数图中实际存在的线的条数/ /图中理论上最多可能产图中理论上最多可能产生的生的 线的条数线的条数”。当图中点的个数为。当图中点的个数为n n时，密度可以表示为时，密度可以表示为l/n(n-l/n(n-1)/2.1)/2. 其中分子其中分子l l是图中实际存在的线的条数，

17、是所有点度数总和的一半，也是图中实际存在的线的条数，是所有点度数总和的一半，也就是就是 邻接阵中所有元素总和的一半。而分母可以用简单的排列组合方邻接阵中所有元素总和的一半。而分母可以用简单的排列组合方法计算得到。法计算得到。2.2.点度中心势点度中心势 反映社区内的集中程度，也间接反映核心人物对社区的影响程度。反映社区内的集中程度，也间接反映核心人物对社区的影响程度。 思路：思路： 首先找到图中的最大中心度数值；然后计算该值与任何其他点的中心度的差，首先找到图中的最大中心度数值；然后计算该值与任何其他点的中心度的差， 从而得出多个从而得出多个“差值差值”；再计算这些；再计算这些“差值差值”的总和；最后用这个总和除的总和；最后用这个总和除以各个以各个“差值差值”总和的最大可能值。总和的最大可能值。 公式：公式：好友推荐：把好友关系转化成图的形式，点代表一个用户，连接两点的边代表两个用户是好友，边可以有权重，也可以没有。直接认识的朋友，叫一度好友。朋友的朋友，叫二度好友，而我们主要通过二度好友进行好友推荐，即“朋友的朋友”的思想。 1