一种基于Sketch的Top-k紧密中心性快速搜索算法

在大数据的时代背景下,由于网络数据(network data)能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系,越来越受到工业界和学术界的关注.在社交网络分析任务中,一个基本操作是从网络中发现重要程度前k大的节点.紧密中心性(closeness centrality)是一种常见的节点重要性刻画指标,它用节点在网络中心的程度来反映节点的重要性.用紧密中心性衡量节点重要性进行节点搜索的问题称为top-k紧密中心性搜索问题.然而,传统的精确算法由于其多项式级别的复杂度无法高效地扩展到大规模的网络数据上.近来,研究人员提出了近似算法,通过牺牲结果精度来获得性能提升.通过分析发现,目前存在的近似算法虽然性能得到了有效提升,但是结果精度牺牲过大.为了解决这个问题,该文设计了一种新颖的近似算法,叫做基于Sketch的紧密中心性搜索算法.此近似算法应用了一个全新的计算方式,利用Sketch估计同一距离的邻居数目,然后得到近似的最短距离之和,最终得到各个节点的紧密中心性的估计值.此算法的时间复杂度为O(mt Dmax),其中t是常数,Dmax是网络直径,m是网络边数.根据实际社交网络的小世界现象的特性,此近似算法基本是个线性算法.最后,相比于目前存在的精确算法和近似算法,该文通过全面的实验验证了基于Sketch的紧密中心性搜索算法在时间性能和结果精度等两方面的优势.

融入紧密度中心性与信用的社交网络用户影响力强度计算模型

在社交网络中意见领袖对信息传播有着巨大的促进作用,意见领袖往往能够影响群众以及引导网络舆论的走向。寻找网络中的意见领袖可以及时准确地掌握网络动态。本文提出一种融入紧密度中心性与信用的用户影响力强度计算模型,寻找电商化社交网络中的意见领袖。该模型首先根据用户间的好友关系获得关系邻接矩阵。然后用该邻接矩阵计算每个用户的紧密度中心性。提出SocialCreditRank算法计算用户影响力,该算法选择用户在网络中的紧密度中心性比重作为用户被随机选择的概率,用户与好友的信誉度之比对好友的贡献度进行修正。本文以支付宝的用户数据作为实验对象,实验结果表明该方法比一般的意见领袖识别方法效果更加精确。

基于网络中心性分析的虚拟网络映射算法

定义了有权网络节点紧密度和路径中心度,并提出了基于网络中心性分析的虚拟网络映射算法。该算法是一个两阶段映射算法,从全局角度分别对底层节点和映射路径进行了有效的定量评估,提高了映射资源选择的均衡性。仿真实验结果表明,与现有的主流研究成果相比,该算法显著地提高了虚拟网络请求接受率。

个人微博用户网络的节点中心性研究

以新浪个人微博用户为研究对象,建立了一个"关注"与"被关注"的有向网络.将节点度、紧密度、介数和K-壳4个社会网络指标应用到微博有向网络,研究了个人微博用户网络中节点的中心性,得到网络中重要性用户,分析了他们在信息传播中的作用和在网络中所表现出来的特性,体现出该用户的兴趣爱好.研究了社会网络指标与度之间的相关性,体现出网络各指标之间的关系.研究结果有助于识别个人微博用户网络的关键节点,进而分析信息在个人微博用户网络中的传播.

基于宝鸡公交网络节点的中心性分析

选取陕西省宝鸡市的344个公交站点作为节点,基于复杂网络理论构建了宝鸡公交网络模型.通过分析网络中节点的度中心性、介数中心性以及紧密度中心性指标,对网络中各个节点中心化程度进行研究,从不同的角度确定出宝鸡公交网络中的枢纽节点,对应于城市的关键站点和主要换乘站点.网络节点中心化的研究可为城市公交网络站点的合理分配及公交系统规划提供一定的理论依据.

基于引力模型的广度优先路径搜索算法在全球价值链位置测度中的应用

本文基于亚洲开发银行发布的国家间投入产出数据构建了全球产业价值链网络模型,从经济物理学视角对比了2000年和2019年世界各国产业部门与其上下游产业部门间的紧密程度,考察了产业部门在全球价值链上所处的相对位置。研究表明:(1)全球价值链网络发展整体呈异质性,但后向或前向产业关联中具有竞争优势可促进产业部门在另一侧的竞争优势提升;(2)2000~2019年,各国产业部门的后向和前向紧密度总体呈增长态势,但中国和美国在连接全球价值链中上游供给侧和下游需求侧的作用最为显著;(3)低技术含量、中高技术含量与公共和福利服务产业相对更加贴近上游供给侧,而基础类产业和商业服务类产业相对更加贴近下游需求侧。

Folksonomy中用户标签的语义紧密性研究

借助复杂网络分析技术,基于用户标签间的语义关联关系构建用户标签网络。通过对用户标签网络紧密中心性指标的计算与分析,得出Folksonomy中的用户标签个体间的语义紧密程度接近于随机网络的自由化松散分布特征,而在整体的语义关系方面却拥有趋近于领域本体的较高的语义紧密程度。