【摘 要】
:
世界万物的交互沿着时间维度推进,如电信话务网络、在线社交网络、科学合作网络、知识图谱以及物联网。人们通常将这类附有时间信息的交互网络建模成时序图。与传统的静态图相比,时序图刻画了交互的时间信息。因此,时序图能够更加细粒度的揭示交互的来源和演化过程。其中,挖掘大规模时序图中的稳定社区结构对于深入理解和管理此类网络具有重要的科研意义和应用价值。然而,对时序图中的稳定社区结构的研究面临着两方面的挑战:一
论文部分内容阅读
世界万物的交互沿着时间维度推进,如电信话务网络、在线社交网络、科学合作网络、知识图谱以及物联网。人们通常将这类附有时间信息的交互网络建模成时序图。与传统的静态图相比,时序图刻画了交互的时间信息。因此,时序图能够更加细粒度的揭示交互的来源和演化过程。其中,挖掘大规模时序图中的稳定社区结构对于深入理解和管理此类网络具有重要的科研意义和应用价值。然而,对时序图中的稳定社区结构的研究面临着两方面的挑战:一方面,现有的社区模型不能刻画时序图中社区的稳定性。适应时序图的稳定社区定义需综合考虑子图在时序稠密性和时序稳定性两方面的关联特性,因而时序图上的稳定社区的建模更加复杂。另一方面,由于交互是以所参与节点及其发生时间共同区分,所以时序图的规模往往比对应的静态图大,从而严重的增加了时序图中稳定社区挖掘问题的计算复杂度。能同时克服这两方面挑战的研究尚不多,且存在一定的不足。为此,对大规模时序图中的稳定社区结构进行了深入的探究,所取得的主要研究成果总结如下:在拟团(Quasi-Clique)的基础上,提出了一种新的极大稳定社区模型——极大的ρ-稳定-(δ,γ)-拟团(Maximalρ-Stable-(δ,γ)-Quasi-Clique,SQC)。SQC要求发现的全部稳定社区彼此不包含,从而保证了结果中每个稳定社区的极大性。但找出所有的SQC是一个NP-难问题。为此,先设计了一个近似线性时间复杂度的时序图削减算法(Temporal Graph Reduction Algorithm,TGRA)来减小原始时序图的规模。在削减之后的时序图上,采用分而治之的算法框架,并辅之四个高效的剪枝策略来削减搜索范围。实验结果表明TGRA能削减原始时序图98%的节点,以及所设计的最佳算法性能比基线算法快2个数量级以上。此外,案例分析以及定性分析证实了SQC模型的有效性。在k核(k-Core)的基础上,提出了一种新的多样化稳定社区模型——多样化的前r个稳定-(k,σ)-核(Diversified Top-r Stable-(k,σ)-Core,DSC)。DSC要求找出的r个稳定社区能最大程度上覆盖顶点和时间戳,从而保证了结果社区的多样性。由于挖掘DSC是一个NP-难问题,所以高效的计算精确解不可行。考虑到DSC是一个次模函数,基于贪婪的思想设计了近似比为(1-1/e)的算法Gre SC。然而,Gre SC具有极高的时间和空间复杂度,导致可扩展性差。因此,进一步的提出了近似比为1/4的懒惰更新算法Top SC。实验结果表明Top SC实际的多样化质量与Gre SC相当,以及所设计的最佳算法性能比基线算法快1-3个数量级。此外,案例分析以及定性分析证实了DSC模型的有效性。在时间受限的个性化PageRank的基础上,提出了一种新的局部稳定社区模型——时序感知的局部稳定社区(Temporal-Aware Stable Community Search,TACS)。TACS要求所发现的稳定社区中的顶点与给定的查询顶点在结构和时序上高关联,从而保证了结果社区的局部性。首先,设计了一个近似线性时间复杂度的贪婪移除的精确算法(Exact Greedy Removing Algorithm,EGR)。然而,EGR是全局算法,不利于在线的局部稳定社区发现。因此,进一步的提出了两阶段局部搜索的近似算法(Approximate Two-Stage Local Search Algorithm,ALS)。ALS通过从查询点出发来局部地探索时序图。实验结果表明EGR和ALS能在1分钟内找出目标社区,但基线算法却在两天内不能得到结果。在大多数数据集下,ALS比EGR快2-4倍。此外,案例分析以及定性分析证实了TACS模型的有效性。综上所述,针对时序图中稳定社区挖掘这个研究命题,提出了三个新颖的模型:极大稳定社区、多样化稳定社区和局部稳定社区。同时,所提出的挖掘方法能为社区挖掘研究者提供新的视角。
其他文献
混凝土是一种应用极为广泛的人造复合材料,其损伤和断裂性质决定了许多工程结构的可靠性与安全性。混凝土结构的宏观损伤开裂行为与其非均质微观结构紧密相关。混凝土结构损伤断裂的模拟仿真通常有两种模型:均质化模型和显式非均质微结构模型。对于材料的非线性行为,特别是涉及应变局部化和断裂等情况,均质化模型得到的结果不一定正确。显式非均质化模型受限于计算量,不适用于具有极小微观相的宏观构件。本文在近场动力学(Pe
碳化硅(Silicon Carbide,SiC)功率器件相比硅基器件具有更高的开关速度和更低的开关损耗,有助于提高电力电子变换器的效率和功率密度,但高开关速度会加剧寄生参数对开关损耗和电磁干扰(Electromagnetic Interference,EMI)的影响。针对这一问题,本文通过理论计算、仿真分析、实验验证的方法研究了寄生参数对开关损耗和传导EMI的影响规律,并通过改进封装结构的方法对S
航空结构件和发动机大叶片等薄壁类零件是航空航天领域的关键零部件,通常这些零件的设计尺寸、轮廓精度和表面质量要求高,目前高速数控铣削技术仍是其主要加工手段。然而由于薄壁工件属于典型的弱刚性构件,铣削过程中工件与刀具之间极易发生颤振现象,进而导致刀具加速磨损,工件表面质量恶化。因此建立铣削稳定域图提前优选无颤振的工艺参数,同时在加工过程中进行振动监测和参数优化控制,对实现弱刚性构件的高效高品质加工具有
光的偏振态能够反映出物质的多重物理信息,因此光的偏振探测技术在信息时代具有重要的意义。然而,传统的偏振分辨光电探测器往往依赖于特定结构的光学介质,制备较为复杂且不利于器件的集成。而新兴的基于材料本征各向异性结构的偏振分辨光电探测器则更侧重于对线偏振光的检测。因此,探究新型的具有圆偏振光分辨能力的材料,将为偏振分辨光电器件的发展带来新的机遇。手性二维有机-无机杂化钙钛矿具有本征的手性特性和光学各向异
作为数控机床、机器人、先进轨道交通装备等国家战略领域的核心部件,基于电力电子变换器的现代交流电机驱动系统近年来得到了快速发展。为了满足这些高端装备对功率密度、调速范围和故障容错等方面日益增长的严苛性能要求,新型拓扑结构和相应的控制算法设计成为了国内外电力电子与电力传动领域的研究热点。其中,开绕组交流电机驱动系统,因具有调速范围宽、动态响应快、控制自由度高、容错运行能力强等优势,近年来受到了学术界和
在生命科学研究中,荧光显微成像技术因其能够对特异性标记的生物样本成像而成为一种重要的微观结构观测工具。在脑科学、神经生物学、临床医学研究中,对如小鼠鼠脑、肺等数毫米尺度的完整器官进行单细胞级分辨率成像对显微荧光成像提出了挑战。近年来,光片荧光显微镜成为一种被广泛应用的三维荧光成像方式,其层析照明的方式能够带来更高的轴向分辨率和成像通量,能够对生物的组织和器官三维成像。然而,传统的高斯光片显微镜在对
近年来,中国经历了大规模的快速城镇化进程,并且已经取得了斐然成绩。在人口向城市大量集中的过程中,城市空间不可避免地需要不断扩容,才能更好承载日益密集的社会经济活动。当前,中国城镇化已经处于快速发展阶段的收尾期,正在转向全面提升质量的新阶段,有必要对中国城市空间扩张的图景、机制以及相关路径进行系统展现、科学论证以及客观评估,从而全面有效地推动城镇化高质量发展。论文首先从时间和空间两个维度,在全国、区
绝缘体上硅材料可以利用成熟微电子工艺制造大规模光电器件,在数据中心及片上等短距离光互连扮演着重要角色。模式复用技术能够利用多个空间模式作为独立传输信道,是应对波分复用多波长光源硅基集成难题及其附带的成本和能耗问题的极具潜力方案。本文的研究对象是硅基多模Y分支及其模式调控技术,目的是为了提高片上光互连通信容量的同时,更为灵活高效地优化调配信道资源。硅基多模Y分支基于绝热演化机制调控模式,在理论上具有
光纤激光器具有方向性好、抗干扰能力强、光学效率高、易于热管理、结构紧凑等优势,因而已经被广泛应用于通信、传感、材料加工、生命科学、国防军事、航空航天等领域。作为一种新型的光纤激光器,随机光纤激光器由于其独特的腔结构、光学特性、制作简单、成本低、以及在光学成像和光纤传感等方面的巨大应用潜力,使得其在最近的十年里获得了研究人员的广泛关注。利用随机光纤光栅提供随机反馈的随机光纤激光器,由于在泵浦阈值、光
水电机组是水能资源开发利用的核心装备,承担着电力系统调峰、调频、调相以及事故备用等关键任务,因此机组运行工况切换频繁,且各工况参数的变化时间尺度不一致,复杂多变的工况条件为掌握机组运行状态及保障机组安全高效运行带来了较大困难。为此,本文以计算流体力学、人工智能以及智能优化等先进方法为理论背景,以物理驱动的模型仿真与数据驱动的机器学习为技术手段,从水电机组运行状态仿真、监测数据增强、性能状态评估以及