摘要:现有的超图网络表示方法需要分析全批量节点和超边以实现跨层递归扩展邻域, 这会带来巨大的计算开销, 且因过度扩展导致更低的泛化精度. 为解决这一问题, 提出一种基于重要性采样的超图表示方法. 首先, 它将节点和超边看作是两组符合特定概率测度的独立同分布样本, 用积分形式解释超图的结构特征交互; 其次, 设计带可学习参数的邻域重要性采样规则, 根据节点和超边的物理关系和特征计算采样概率, 逐层递归采集固定数目的对象, 构造一个更小的采样邻接矩阵; 最终, 利用蒙特卡洛方法近似估计整个超图的空间特征. 此外, 借鉴PINN的优势, 将需要缩减的方差作为物理约束加入到超图神经网络中, 以获取更具泛化能力的采样规则. 多个数据集上的广泛实验表明, 所提出的方法能够获得更准确的超图表示结果, 同时具有更快的收敛速度.

摘要:复杂网络在现实场景中无处不在，高效的复杂网络分析技术具有广泛的应用价值，比如社区检测、链路预测等.然而，很多复杂网络分析方法在处理大规模网络时需要较高的时间、空间复杂度.网络表征学习是一种解决该问题的有效方法，该类方法将高维稀疏的网络信息转化为低维稠密的实值向量，可以作为机器学习算法的输入，便于后续应用的高效计算.传统的网络表征学习方法将实体对象嵌入到低维欧氏向量空间中，但复杂网络是一类具有近似树状层次结构、幂率度分布、强聚类特性的网络，该结构更适合用具有负曲率的双曲空间来描述.针对复杂网络的双曲空间表征学习方法进行系统性的介绍和总结.

摘要:在复杂网络理论中，core分解是一种最基本的度量网络节点重要性并分析核心子图的方法.Core分解广泛应用于社交网络的用户行为分析、复杂网络的可视化、大型软件的代码静态分析等应用.随着复杂网络的图数据规模和复杂性的增大，现有研究工作基于多核CPU环境设计core分解并行算法，由于CPU核数和内存带宽的局限性，已经无法满足大数据量的高性能计算需求，严重影响了复杂网络的分析应用.通用GPU提供了1万以上线程数的高并行计算能力和高于100GB/s访存带宽，已被广泛应用于大规模图数据的高效并行分析，如广度优先遍历和最短路径算法等.为了实现更为高效的core分解，提出面向GPU平台下的复杂网络core分解的两种并行策略.第1种RLCore策略基于图遍历思想，利用GPU高并发计算能力对网络图结构自底向上遍历，逐步迭代设置各节点所属的core层；第2种ESCore策略基于局部收敛思想，对各节点从邻居节点当前值进行汇聚计算更新直至收敛.ESCore相比RLCore能够大大降低遍历过程中GPU线程更新同一节点的同步操作开销，而其算法的迭代次数受收敛率的影响.在真实网络图数据上的实验结果表明，所提出的两个策略在效率和扩展性方面能够大幅优于现有其他方法，相比单线程上的算法高达33.6倍性能提升，且遍历边的吞吐性能（TEPS）达到406万条/s，单轮迭代的ESCore的执行效率高于RLCore.

摘要:社团结构划分对复杂网络研究在理论和实践上都非常重要.借鉴分布式词向量理论，提出一种基于节点向量表达的复杂网络社团划分方法（CDNEV）.为了构建网络节点的分布式向量，提出启发式随机游走模型.利用节点启发式随机游走得到的节点序列作为上下文，采用SkipGram模型学习节点的分布式向量.选择局部度中心节点作为K-Means算法的聚类中心点，然后用K-Means算法进行聚类，最终得到社团结构.在真实和模拟两种网络上做了丰富的实验，与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上CDNEV算法的F1指标比其他算法平均提高19%；在模拟网络上，F1指标则可以提高15%.实验结果表明，相对其他算法，CDNEV算法的精度和效率都较高.

摘要:社区发现是当前社会网络研究领域的一个热点和难点，现有的研究方法包括：（1）优化以网络拓扑结构为基础的社区质量指标；（2）评估节点间的相似性并进行聚类；（3）根据特定网络设计相应的社区模型等.这些方法存在如下问题：（1）通用性不高，难以同时在无向网络和有向网络上发挥出好的效果；（2）无法充分利用网络的结构信息，在真实数据集上表现不佳.针对上述问题，提出一种基于节点不对称转移概率的网络社区发现算法CDATP.该算法通过分析网络拓扑结构来设计节点转移概率，并使用random walk方法评估节点对网络社区的重要性.最后，以重要性较高的节点作为核心构造网络社区.与现有的基于random walk的方法不同，CDATP为网络中节点设计的转移概率具有不对称性，并只通过节点局部转移来评估节点对社区的重要程度.通过大量仿真实验表明，CDATP在人工模拟数据集和真实数据集上均比其他最新算法有更好的表现.

摘要:提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（detecting overlapping communities over complex network big data），时间复杂度为O（nlog2（n）），算法基于模块度聚类和图计算思想，应用新的节点和边的更新方法，利用平衡二叉树对模块度增量建立索引，基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法，对每个节点分析的频率大为降低，可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区，社区识别准确率较高，在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97，重叠节点检测指标F-score的平均值在0.91以上，且复杂网络大数据下的运行时间明显优于传统算法.

摘要:目前，针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区，然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重，这些先验信息对社区发现的准确性至关重要.针对该问题，提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks，简称OCDW）.首先，综合考虑网络拓扑结构及真实网络中边权重的影响，给出了一种网络中边的权重定义方法；进而给出种子节点选取方式和权重更新策略；最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较，结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.

摘要:随着分布式计算技术的发展,以自治的服务协同与互操作为主要构造手段、结构与行为随需而变的面向服务的软件系统已成为当前主流的软件架构,分析并理解服务交互行为对于这类复杂软件系统的开发、维护和运营具有重要意义.针对面向服务的软件系统中基本构成元素Web服务的复杂交互执行行为,考虑到服务自治性及系统规模化所带来的复杂性,借鉴复杂网络建模分析方法,提出了一种考虑服务行为特征的服务动态行为生长演化模型.模型首先以真实服务的服务结构数据为基础,以服务间参数关联关系为核心,通过参数匹配建立服务结构网络作为基本连通性约束,代表可能发生交互关系的服务.然后,基于服务间的择优选择、组合交互及动态重组等特性,对面向服务的软件系统生长演化及动态执行行为进行了仿真建模.在Seekda及QWS数据集上进行了仿真实验,结果表明:与传统的软件系统的层次性结构有所不同,由自治的Web服务所构成的软件系统具有更强的模块性;与系统中个体服务演化规则,如择优连接及动态重组相比,服务结构网络的性质对系统最终形态有更重要的影响,相关结果对大规模服务软件的构建及分析具有重要的指导意义.

摘要:将目标形状的轮廓看成一个无序的点集，从中抽取形状特征，用于快速而有效的目标识别是形状分析任务中的挑战性问题.针对该问题，提出了一种基于复杂网络模型的形状描述和识别方法.该方法提出用一种自组织的网络动态演化模型构成一个分层的描述框架，在网络动态演化的每一个时刻，对网络分别进行局部测量和全局测量，抽取网络的无权特征和加权特征.在形状匹配阶段，用获得的局部描述子和全局描述子分别进行局部匹配（基于Hausdorff距离）和全局匹配（基于L1距离），组合两种匹配的距离值构成对形状的差异度度量.用标准的测试集对所提出的方法进行性能测试，实验结果表明，所提出的算法能够快速而又鲁棒地完成较高精度的形状识别任务.

摘要:针对典型复杂网络模型仅描述了复杂系统中同一类个体及其间一种相互关系且对问题的讨论仅局限于同一个系统的问题,基于能够描述复杂系统中异类个体间多种关系的多子网复合复杂网络模型,导入多维向量空间,将网络节点间的关系映射为多维向量,定义了向量复合网.在此基础上,将该模型的动态组网运算(加载与退缩)转化为向量空间的基变换,给出了加载运算与退缩运算的形式描述,实现了多子网复合复杂网络的可计算.建立并分析了我国铁路客运复合网,通过网络动态重组运算,基于高速铁路子网与低速铁路子网的拓扑性质,给出了我国铁路发展现状分析.