基于节点分类排序的社交网络图压缩算法

发布时间：2021-10-24 03:03

　　近年来,社交网络图分析受到广泛关注,然而由于内存的限制,规模不断增长的社交网络图已经无法完整放入内存,这对其存储和分析都带来了挑战。图压缩通过减少存储空间需求为应对这个挑战提供了一种行之有效的解决方法。现有面向社交网络图应用的压缩算法多种多样,有的采用复杂编码技术提升压缩率但无法保证图算法的运行性能、有的采用简单编码技术保证图算法的运行性能但牺牲了压缩率,无法兼顾二者。为解决上述问题,社交网络图压缩算法需要对节点排序以挖掘影响社交网络图压缩率的关键属性从而提升压缩率,并采用简单编码技术保证图算法的运行性能。现有研究已经证实社交网络图的压缩率高度依赖于局部性,而目前挖掘局部性的节点排序算法未考虑到不同节点对局部性的不同影响,仅能挖掘出一部分局部性。本项研究提出了一种基于节点分类的混合排序算法,对高度节点、低度节点、零度节点分别采用不同排序策略,挖掘出更多区域的局部性,提升可压缩范围;采用上述算法提出了一种基于节点分类排序的社交网络图压缩算法NCOGC,既能获得良好的压缩率又能保证图算法在线有效运行;实现了以广度优先搜索（BFS）、网页排名（PageRank）为代表的典型图处理算法,以验证... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：56 页

【学位级别】：硕士

【部分图文】：

LogGap与压缩率的关联

华 中 科 技 大 学 硕 士 学 位 论 文关注很多的人，而多数普通人则只关注自己圈子里的人。本节以 Twitter 为例分析社交网络中的无标度性质，Twitter1是一家著名的社交网络及微博客服务的网站，网络中的节点表示 Twitter 用户，网络中的边表示 Twitter 用户之间的友谊。图 2-2 展示了Twitter 中节点的入度分布和出度分布，横坐标为节点的度大小，纵坐标为具有该度大小的节点个数，横坐标和纵坐标均为对数刻度。可以看到多数节点具有很低的度，少数节点具有很高的度，入度和出度都呈现幂律分布。社交网络图中也存在一些零度节点，零度节点不存在于其他节点的邻居中，如果这些节点不连续，会分散图节点的其他邻居，降低局部性。

中 科 技 大 学 硕 士 学 位 用户，网络中的边表示 Facebook 用户之间的友谊etworkX 中的绘图工具对 Ego-Facebook 进行可gold[33]力导向算法定位节点的布局方式 spring_la色部分表示网络中的节点，灰色部分表示网络中多个社区，社区内连接紧密，社区间连接微弱，区连接成了一个更大的组件，这和 Kang 描述的交网络图中社区内的边位于图邻接矩阵对角区域部性，社区内联系越紧密，图邻接矩阵对角区域数枢纽节点具有多数边，这些边位于图邻接矩阵部性。

【参考文献】：
期刊论文
[1]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉.  软件学报. 2014(09)
[2]在线社交网络影响力分析[J]. 吴信东,李毅,李磊.  计算机学报. 2014(04)



本文编号：3454448