计算机设计大赛炫酷展示PPT课件.ppt

基于web的社会网络可视化分析平台 背景与意义 功能介绍 技术知识 创新之处 1 未来展望 目录 背景与意义 社会网络 socialnetwork 是由图表示的异构多关系数据集 图中节点对应对象 边对应表示对象间联系或相互作用的链接 过去的几十年间 社会网络受到越来越多的关注 特别是移动网络和互联网的发展 产生了大量的 容易被计算机处理的社会网络数据 从这些数据中获取知识 从而理解商业行为 识别业务模式 捕捉用户行为 更好利用资源 提高服务质量 将成为运营商的核心竞争力之一 对于现在大数据的时代中 挖掘出社交网络上的社区很有实用价值 社区内用户的共同话题 会形成一个定向的区别用户的方式 为智能搜索 个性化服务 商业应用推广等应用提供理论依据 从广告投放的角度来看 容易找到定向的广告受众 从朋友推荐的角度看 能够方便的将同一个社区内的个体向其他个体进行推荐 为找寻多年没有联系的朋友提供一个方便快捷的途径 背景与意义 将社会网络分析以一种数据可视化的形式展示给决策者 不仅能形象直观 还有助于其在庞大的数据中能及时捕获所需信息 数据可视化 是关于数据之视觉表现形式的研究 如今 可视化已经不仅仅是点和线的简单描绘 它成为了一种能传递深层数据内涵 启发问题解决方案的强大智能模型 类似这样的软件 在国外著名的有UCINET Pajek以及Gephi等 UCINET Pajek侧重于社会网络的分析 但可视化的效果较差 而且操作不简单 忽略用户体验 Gephi是则偏向于社交图谱的数据可视化 能生成漂亮的可视化图形 并对数据进行清洗和分类 但数据分析不够全面 提供算法较少 另外 这些软件都需用户下载才能使用 不支持web端 这样导致电脑因系统的差异而使用不了某些软件 如Gephi需jdk1 7以下的环境配置 不支持jdk1 8 针对上述的不足 我们小组研发了一个基于web端的社会网络可视化分析平台 名为vina 力求将社会网络分析与数据可视化充分结合 以给用户更好的体验效果 功能介绍 项目简介 本系统是一个基于开源框架Django的社会网络可视化分析网站 并且尽可能简单灵活地使数据可视化 特点是UI美观 使用简单 支持大多数浏览器 支持多种文件格式的输入 提供多种社区划分算法 数据可视化的结果包括了网络图 柱状图 饼图 表格 让用户从不同角度获得社区网络划分的结果 另外 本系统还运用了社会网络分析的知识 为用户挖掘出网络中的重要信息 本系统的用途可分为 客户群体细分 社交网络分析 热点事件分析 舆情监控 社会网络划分的教学等 功能介绍 项目特点 功能介绍 项目用途 功能介绍 系统使用流程 本系统的网址为http 120 25 203 152 8000 项目的功能介绍 文件导入格式 我们导入的文件有两个 第一个是网络信息文件 文件的内容以source target weight为格式 source代表源点 target代表目标点 weight代表连边权重 例如节点1对节点6有连边 连边权重为2 我们记录的格式为 1 6 2 第二个是节点标签文件 文件的内容是节点所对应的标签 以node label为格式 例如节点1的标签叫quincy 两份文件均支持txt xls和csv格式 网络信息文件 标签文件 LPA BGLL WALK TRAP FAST GREEDY 技术知识 社区划分算法 四种算法都具有良好的社区划分效果 不同的算法适用于不同的场景 BGLL 稳定准确 Walktrap 划分效果好 Fastgreedy 适用大型加权网络 技术知识 算法特点 技术知识 1 labelpropagationAlgorithm LPA 标签传播算法 LPA 是由Zhu等人于2002年提出 它是一种基于图的半监督学习方法该算法的基本原理如下 首先 给全网每个节点分配一个不重复的标签 label 其次 在迭代的每一步 让一个节点采用在它所有的邻居节点中最流行的标签 如果最佳候选标签超过一个 则在其中随机抽一个 最后 在迭代收敛时 采用同一种标签的节点被归入同一个社区 这个算法的核心是通过标签的扩散来模拟某种流在网络上的扩散 其优势是算法简单 特别适用于分析被流所塑造的网络 在大多数情况下可以快速收敛 其缺陷是 迭代的结果有可能不稳定 尤其在不考虑连边的权重时 如果社区结构不明显 或者网络比较小时 有可能所有的节点都被归入同一个社区 Reference Raghavan U N andAlbert R andKumara S Nearlineartimealgorithmtodetectcommunitystructuresinlarge scalenetworks PhysRevE76 036106 2007 http arxiv org abs 0709 2938 技术知识 2 BGLL这个方法分两步 1 从节点合并开始 构建第一步社团划分结果 每个节点根据模块度增益决定是否加入到邻居节点的社团中和到底加入到哪个邻居节点的社团中 每个节点按序执行该过程 2 重新构建网络 把第一步每个社团单做一个节点 边是原来社团之间链接边权的和 3 迭代 1 2 直到收敛 Reference VDBlondel J LGuillaume RLambiotteandELefebvre Fastunfoldingofcommunityhierarchiesinlargenetworks JStatMechP10008 2008 http arxiv org abs 0803 0476 技术知识 3 Walktrap算法的初始条件为每个结点为一个单独的社区 然后逐步合并可使结点和它所在社区之间的平方距离均值达到最小的两个社区 每一步都要更新社区之间的距离 其中两个结点之间的距离对应于它们的相似度 即在一个离散的随机游走过程中 它们之间的方向转移概率 Reference PascalPons MatthieuLatapy Computingcommunitiesinlargenetworksusingrandomwalks http arxiv org abs physics 0512106 技术知识 4 Fastgreedy一种基于贪婪法思想的凝聚算法 并称这种算法为快速算法 将网络划分为K个社团 定义一个k k维的对称矩阵E 其中元素 表示网络连接两个不同社团的节点的边在所有边中占的比例 这两个节点分别位于第i个社区和第j个社区 1 初始化网络为N个社团 即每个节点就是一个独立社团 2 依次合并有边相连的社团对 并计算合并后的模块度增量 根据贪婪算法的原理 每次合并应该沿着模块度增大最多或者减少最少的方向进行 每次合并以后 对对应的元素更新 并将与i j社团相关的行和列相加 3 重复步骤2 不断合并社团 直到整个网络都合并为一个社团 4 整个算法完成后 得到一个社区结构分解的树状图 再通过选择在不同位置断开可以得到不同的网络社区结构 在这些社区结构中 选择一个对应局部最大模块度值的结构 就得到最好的网络社区结构 Reference A Clauset M E J NewmanandC Moore Findingcommunitystructureinverylargenetworks PhysRevE70 066111 2004 技术知识 社区划分通过社区划分算法将一个网络划分成不同社区 同一个社区的节点联系较为紧密 不同社区的节点联系较为稀疏 效果如下 社区结构分析 核心人物挖掘 好友推荐 技术知识 核心人物挖掘 中心性分析 描述图中任何一点在网络中占据的核心性源于社会计量学的 明星 概念 一个核心点是那种处于一系列关系核心的位置 即该点与其他点有众多的直接联系 若某点具有最高点度中心度 则称该点居于中心 我们通过点度中心度挖掘出网络中核心人物 而点度中心度可分为绝度中心度和相对中心度 一般采用相对中心度较为准确 技术知识 社区结构分析 1 社区密度 反映社区内的紧密程度 密度值0到1之间 越接近1则代表彼此关系越紧密 一般将密度定义为 图中实际存在的线的条数 图中理论上最多可能产生的线的条数 当图中点的个数为n时 密度可以表示为l n n 1 2 其中分子l是图中实际存在的线的条数 是所有点度数总和的一半 也就是邻接阵中所有元素总和的一半 而分母可以用简单的排列组合方法计算得到 2 点度中心势反映社区内的集中程度 也间接反映核心人物对社区的影响程度 思路 首先找到图中的最大中心度数值 然后计算该值与任何其他点的中心度的差 从而得出多个 差值 再计算这些 差值 的总和 最后用这个总和除以各个 差值 总和的最大可能值 公式 技术知识 好友推荐 把好友关系转化成图的形式 点代表一个用户 连接两点的边代表两个用户是好友 边可以有权重 也可以没有 直接认识的朋友 叫一度好友 朋友的朋友 叫二度好友 而我们主要通过二度好友进行好友推荐 即 朋友的朋友