• 1. 基于随机游走和标签传播 的社区发现算法研究答辩人:余 跃导 师:苏 畅2015年5月30日专 业:计算机技术
  • 2. 目录研究背景1我的工作2总结及未来工作3①基于随机游走的标签传播社区发现算法 ②基于mapreduce的随机游走 ③基于mapreduce的标签传播
  • 3. 研究背景标签传播社区发现算法一种利用网络拓扑结果引导社区发现过程,不需要社区数目、大小等先验信息。具有接近线性时间复杂度,适用于大规模网络中的社区发现。社区发现算法就是对节点进行分类,挖掘复杂网络中的隐藏信息。同一个社区中节点具有相似的特性和社会信息。客户流失预测、商品推荐、舆情分析。对万维网中的网页进行分类,有助于提高搜索效率和精确度,有助于信息过滤、热点追踪、新闻分析。基于标签传播社区发现算法中标签是节点社区归属的标志,标签相同的节点在一个社区。社区发现的应用1231/25
  • 4. 研究现状分列式层次聚类算法:GN算法(2002) 凝聚式算法(2004,2005) 标签泛洪法(2005) 谱二分法(2006)LPAp(2014)HANP算法(2009) DAPA(DDALPA,ODALPA)(2011)LPA算法(2007)时间复杂度较高, 难以扩展到大规模网络中Monster社区随机性问题122/25
  • 5. 随机性问题LPA算法更新标签时出现的随机性问题 LPA算法多次对空手道俱乐部社区发现的结果,颜色相同的节点属于同一社区3/25
  • 6. 基于随机游走的标签传播社区发现算法4/25Xpath定位标签中的内容通过关系对象映射操作数据库存入的是字典类型的数据123踩点豆瓣top250网页,确定需要提取的内容定义item字段,将爬取到的内容保存到item容器中定义pipelines中连接并将数据存入到mongodb中Django服务器从mongodb中取出所有数据,渲染到web页面中4
  • 7. 节点重要性的衡量邻接矩阵,表示某节点与网络中其他节点的连边情况邻接矩阵,表示游走者从某节点游走一步后停留在网络中其他节点概率15/25
  • 8. 节点重要性的衡量1游走者从一个节点位置出发,一直不停的走…,直到自己的位置概率趋于稳态稳态的标志,相邻两步游走者停留在节点i的位置概率小于ε,之后节点开始有了权重6/25
  • 9. 社区种子的筛选与中心节点的初始化36581247…降序排序序列门限值2根据节点权重值降序排序门限值的选择,既要选择能够选择出足够多的社区种子,又要能够较为正确的预处理中心节点7/25
  • 10. 社区种子的筛选与中心节点的初始化2筛选社区种子的算法为网络中的节点添加自环社区种子与中心节点的共同邻居权重和8/25
  • 11. 社区种子的筛选方法Grin,权重值:0.0383; Topless,权重值:0.0351; Kringel,权重值:0.0286; Jet,权重值: 0.0273; Upbang,权重值: 0.0213 社区种子:Grin和Topless的共同中心节点:SN4,权重值:0.035129/25宽温海豚网络
  • 12. 标签传播3节点更新标签的顺序,迭代的从社区种子出发更新节点标签传播的规则,选择邻居节点中权重之和最的标签作为自己的标签10/251
  • 13. 算法测试结果34,俱乐部中的主管,权重值:0.1089; 1,俱乐部中的教练,权重值:0.1026;社区种子:算法对空手道俱乐部社区发现的结果,节点数目34,边数78,节点表示俱乐部里的成员,边表示成员之间的交互11/25
  • 14. 算法测试结果算法对宽温海豚网络社区发现的结果,节点数目62,边数159,节点海豚,边表示海豚之间的亲密关系Grin,权重值:0.0383; Trigger,权重值:0.032; Jet,权重值: 0.0273; 社区种子:12/25
  • 15. 算法测试结果算法对科学家合作网络社区发现的结果,节点数目118,边数200,科学家,科学家之间的科研合作研究RNA结构研究统计物理学Agent-based modelsMathematical Ecology13/25
  • 16. 算法测试结果社区发现算法karate数据集dolphins数据集collaboration数据集LPA算法0.8650.7310.576RWLPA(本文算法)0.94110.729ODALPA0.5590.6770.415DDALPA0.9120.5160.576LPAp110.64414/25
  • 17. 基于MapReduce的并行实现算法的时间复杂度程序对节点数目为4039的ego-Facebook网络社区发现时报错15/25
  • 18. 基于mapreduce的并行实现同步的标签的更新策略16/25
  • 19. 基于mapreduce的随机游走数据流键/值对: map()reduce()17/25
  • 20. 基于mapreduce的标签传播节点更新标签的规则:选择其邻居节点中权重值最大的邻居节点标签作为自己的标签。当所有节点的标签都不再发生变化时算法终止。键/值对: 18/25
  • 21. 测试数据集节点数目边数目平均聚类系数三角形数目最大最短路径4039882340.605516120108ego-Facebook数据信息节点表示调查参与者facebook的id,边表示好友关系,社区表示调查参与者及其社交圈19/25
  • 22. 实验平台硬件CPUIntel(R) Core(TM) i3-4150 CPU @3.5GHz 内存4.00GB硬盘500GB软件操作系统Win7 CentOS开发平台eclipse JDK:Java6 VMware Workstation Hadoop-1.1.2.tar.gz PieTTY、WinSCP20/25远程桌面登录CentOS文件目录可视化
  • 23. 随机游走实验结果概率差的绝对值=|0.07326483-0.07325529|=0.00000954<0.00001,实验中每个节点的权重值都扩大了40倍21/25每一个part-r-0000…文件表示随机游走一步后的输出文件目录
  • 24. 标签传播实验结果22/25每一个output表示标签传播算法迭代一次输出的结果
  • 25. 标签传播实验结果社区编号节点数目节点所占比例社区平均大小107247761.33%      807.8191275018.57%343758214.41%6861714.23%3980591.46%23/25社区节点分布
  • 26. 总结和展望选用随机游走过程衡量节点的重要,减小了节点在根据邻居节点选择更改标签时出现的随机性问题。论文改进了一种社区种子的筛选方法。提出了通过共同邻居节点权重和来限制中心节点成为社区种子,防止社区的分裂。基于mapreduce的并行实现,将程序扩展到hadoop平台,使程序能够处理更大数据集应该拓展出一种动态的策略根据不同类型的网络衡量节点的重要性,筛选网络的社区种子等等。未来的工作对于基于随机游走的标签传播社区发现算法的并行实现需要时间开销更小的分布式并行运行平台如spark等等。24/25
  • 27. 正在更新标签的节点集合S1更新过标签的节点集合S2123下一次更新标签的节点集合 NextExpanding社区种子集合下一次更新标签的节点集合 NextExpanding下一次更新标签的节点集合 NextExpanding…
  • 28. 声卡消息队列百度云语音识别服务器GUI界面Wav音频采集线程从声卡中读取音频信息,存储到磁盘中Wav名称被放入到了消息队列中,音频发送线程从消息队列中读取音频名称,根据名称从磁盘中读取音频文件构建url,header,以post的方式,将wav音频信息发送出去解析服务器返回的json文件,将识别的结构返回的gui界面中
  • 29. (本页无文本内容)
  • 30. 引入静音检测和滤噪功能的背景是: 录音线程一直在不停地向硬盘写入文件,无论麦克风是否采集到音频文件,由于录音线程不停写入文件,导致消息队列中一直有数据,音频发送线程也被迫一直工作,很多无效数据被上传到了云端,浪费api调用次数和时间采用的方法是: 设置两个门限值,一个是采样点的门限值,一个是有效录音的门限值,大于采样门限值的采样点为有效采样点,每次从声卡中读取到缓存中的有效采样点数目大于录音门限值的话为有效录音,否则则为静音。
  • 31. 本地维护终端BAM后台高斯数据库本地维护终端先登录到omu上,再下发配置命令到高斯数据库中,mml编辑器中添加的命令和埋进的参数打补丁时将在本地维护终端显示mmlparaser一个mml命令对应 一个数据库表,命令中的参数对应数据库表中的字段
  • 32. imanager U2000网关omu挂载本地维护终端桌面云华为计算云高斯数据库配置命令下发特性查询1返回查询结果(excel)23
  • 33. 谢谢!★感谢苏畅导师的培养! ★感谢实验室全体老师和同学的帮助! ★感谢各位专家评委的聆听与付出! 25/25
  • 34. (本页无文本内容)