【摘 要】
：
随着互联网数据量的增长以及用户交互模式的发展,各种元数据之间逐渐形成一张巨大的网络结构。图模型是数据库和数据挖掘领域常见的用来表示相互关联的元数据数据模型,许多实际应用离不开基于图模型的数据分析管理方法。现实世界的图数据不仅是稀疏的,而且由于节点度数的随机性而常常出现局部密度分布不均匀的特点。在局部密度较大的部分,元数据之间的关联度高于全局平均值,蕴涵的信息量较大,因此在实际的应用中具有较高的商业
论文部分内容阅读
随着互联网数据量的增长以及用户交互模式的发展,各种元数据之间逐渐形成一张巨大的网络结构。图模型是数据库和数据挖掘领域常见的用来表示相互关联的元数据数据模型,许多实际应用离不开基于图模型的数据分析管理方法。现实世界的图数据不仅是稀疏的,而且由于节点度数的随机性而常常出现局部密度分布不均匀的特点。在局部密度较大的部分,元数据之间的关联度高于全局平均值,蕴涵的信息量较大,因此在实际的应用中具有较高的商业价值。基于大规模稀疏图的稠密子图挖掘具有重要的理论研究价值和现实意义。根据约束的类型和力度差异,可以定义很多种不同的稠密子图结构。本文从极大团和k边连接子图这两种密度约束力最强也是应用最广泛的稠密子图入手,研究在大规模稀疏图数据上这两种稠密子图挖掘算法的性能。现有的极大团枚举方法以树形搜索框架为主,在超高度数节点的局部会产生巨大的搜索空间从而成为算法的性能瓶颈。近来的研究尝试用并行化的计算方法来提高极大团枚举算法的速度。然而,如何进行最优图切分使得算法的总计算量最小以及如何处理数据冗余与负载均衡之间的矛盾是算法并行化过程中亟待解决的两个问题。本文对极大团枚举问题的研究主要探究稳定快速且具有良好可扩展性的新型算法框架。首先提出了一个两阶段计算框架——CMC算法,将直接计算所有极大团的目标转化为先计算包含极大团的、范围更大的候选团集合,再通过一次遍历构造一棵逆序字典树来从候选团中提取出所有的极大团。随后提出了位图转化和退化排序两个优化策略对CMC算法的时间和空间复杂度进行优化,使构造候选团的过程在稀疏图上具有线性时间复杂度,提取极大团的时间复杂度也降到最低。最后提出了一个快速且可扩展的并行极大团枚举算法,基于MapReduce框架分别对两个阶段的计算过程进行了并行化设计实现。现有的解决k边连接子图问题的方案分为精确算法和近似算法。前者主要通过迭代地搜索最小切割集来切分连接度小于k的子图,耗时非常长;后者基于s-t连接度理论近似地对全局k连接度的节点进行合并,计算结果的正确率有待提高。由于k边连接子图挖掘问题的搜索范围是不确定的,不能像极大团枚举问题那样通过并行化来提高计算速度,因此在尽量提高算法正确率的前提下缩短计算时间是研究k边连接子图挖掘问题面临的最大挑战。本文对k边连接子图挖掘问题的研究主要探索如何同时提高近似算法的正确率与计算速度。提出了一种局部k-ECC连接度检测的方法,在对全局k连接度的节点进行合并之前抽取局部的k-core结构并检测其局部的边连接度。为了提高连接度检测的准确性,提出了一种精确计算最大s-t流的算法。然后基于连接度检测的结果,提出了有效的分解树剪枝和最大化合并的策略,使得算法能够在较短的迭代次数内收敛。
其他文献
人群定向是通过对用户的行为,找出具有共同特征的潜在用户集合。为了能够帮助企业或广告主挖掘社交网络中潜在用户,本文针对复杂的社交网络关系,进行了不同网络拓扑结构下的潜在用户挖掘研究。本文针对复杂网络的不同拓扑结构,分别就基于用户行为关系网络、基于位置与行为关系的网络和基于兴趣标签与行为关系的网络中的用户挖掘进行了研究,主要研究内容包括:1.基于行为关系网络的用户挖掘,本文重点研究了基于多种行为关系的
当前随着全球经济一体化的发展,越来越多的跨国企业开始将目光放到国际市场上,其通过在海外其他国家中设立子公司或跨国并购的方式来进行海外扩张,从而在国际市场上打造竞争优势。当前,企业的这种海外扩张行为得到了学术界和商业界的广泛关注。即使是对于跨国企业来说,他们绝大部分的生产经营活动却依旧是在母国市场中完成的,也就是说跨国企业具有很高程度的母国足迹。而跨国企业在母国市场上的经营情况是否能够对其后续的海外
胚胎是一个新生命的开始,胚胎发生和发育受到极其严格且精细的调控,以保证传宗接代正常进行。无论动物还是植物,胚胎都被母体组织层层包裹,多年来的研究揭示了胚胎发育过程中周围母体组织形成的微环境对胚胎发育至关重要,特别是早期胚胎发育极其依赖于这种微环境所传递出的发育信号。对动物胚胎的研究表明,母体-胚胎间存在着复杂的信号交流。母体组织发育缺陷或母源性信号分子异常会导致胚胎发育异常或胎源性疾病。植物胚柄连
虽然生成对抗网络（Generative Adversarial Network,简称GAN）已经被广泛应用于很多实际领域,但是GAN仍然存在缺陷导致无法生成高质量的模拟数据。虽然当前GAN的变体尝试解决这个问题,但是他们在实际运用中仍然存在不少问题。现存的GAN的变体或存在梯度负数（如WGAN）或者生成的数据仍然存在相同图片或者图片模糊等问题（如MGAN）。本文研究的对象主要是在三个方面,即如何解
自“大数据”的概念在2005年被提出以来,“大数据”在全球范围内的学术界和商业界掀起一股革新的热潮。空间大数据（SBD）特指具有空间信息的大数据。智能技术和传感器技术的快速发展使得空间大数据成为了目前最具价值的空间产品之一。SBD可以被分为对地观测大数据与人类活动大数据两类。目前,运用先进的技术手段从SBD中提炼知识已经成为学术界以及相关产业中的重要范式;SBD也在地球科学,城市学,环境科学等多个
当前,各国越来越重视空天地网络信息系统（GASNIS）的建设。GASNIS是以空中平台,包括空间站、高中低轨道的卫星、平流层的气球、有人或无人驾驶的飞行器;以及地面平台、包括地面站点或地面移动终端;水域平台,包括海洋观测船舶或有其他特殊任务的船舶为载体所组成。GASNIS是实时获取,传输和处理相关信息为主要任务的网络信息系统。其发展涉及到国家的政治,经济,军事以及民生等各个重要领域。GASNIS是
登革病毒属于黄病毒科黄病毒属的一个血清型亚群,根据其抗原性的不同可以分为5个不同的血清型。同一血清型中又可因为抗原性的差异分为不同的基因型。登革病毒是一种虫媒病毒,其主要通过埃及伊蚊和白纹伊蚊进行传播。登革病毒主要流行于热带和亚热带地区,在亚洲,太平洋群岛及中、南美洲等许多国家均已造成严重的威胁。登革病毒感染人体后主要引起登革热以及发病率和死亡率都很高的登革出血热和登革休克综合征。其中登革热的症状
三维（Three-Dimensional,3D）视频技术的迅速发展,也让三维音频技术受到了广泛地关注。3D音频系统可以重建具有水平方向、垂直方向以及距离共三个空间自由度的空间音效,在空间任意位置生成虚拟声像,提供具有沉浸感的听音体验。传统的3D音频系统主要是基于声道的,如国际标准组织MPEG指定的三维多声道音频参考系统--NHK 22.2,该系统可以通过24个指定空间位置的扬声器播放对应的多声道信
研究背景:放射性骨损伤（Radiation-induced bone injury,RIBI）是四肢恶性肿瘤和口腔颌面部恶性肿瘤放疗后的并发症之一。对于接受放射治疗的患者而言,一方面,其本身可能存在病理性骨折或术后的骨缺损,放射治疗的电离辐射会降低骨折的愈合能力;另一方面,电离辐射还会直接损伤骨组织,导致骨损伤和骨量丢失,进而增加病理性骨折的风险。严重的放射性骨损伤可以导致骨坏死和骨髓炎,此时甚至
恶性肿瘤严重影响患者的身体健康与生活质量,目前肿瘤的治疗仍然是世界性医学难题。由于个体的差异性以及肿瘤的异质性,传统的肿瘤治疗很难彻底根除肿瘤,并会在治疗过程中引起一系列副作用。光热治疗（PTT）,作为一种新型无创肿瘤治疗技术,逐渐引起人们的广泛关注。在近红外激光照射下,PTT通过光热制剂将光能转化为热能,产生局部高温诱导肿瘤细胞凋亡坏死。这种物理治疗手段具备穿透力强,疗效好,毒副作用小等诸多优点