随着互联网应用的日益普及,越来越多的大数据应用问题采用图来表示其数据结构。图(graph),也被称为网络(network),是一种重要的数据结构。在传统的图模型中,节点为单一类型,例如,商品,用户等;边也为单一类型,表示两个节点的关系,如好友关系等。社区是图中的一组顶点集合,其内部节点间联系较内部与外部节点间联系更为紧密。k-核是一种社区,由于其简洁的定义和高效的算法而被广泛采用。k-核社区发现和搜索是两类基于图的重要问题。以往对这两类问题的研究都是基于传统的图模型。随着应用问题的复杂,一些问题使用传统的图模型难以表达,例如,社交网络中,人们想要找到物理位置接近,同时互为好友关系的那些用户,而这种问题通常可以采用多层网络中的k-核社区来建模。多层网络的各层中共享顶点,具有不同类型的边。不同的层表示系统中顶点之间不同方面的交互关系,从而能够表达更为广泛的概念和更复杂的问题。因此,近年来,多层网络的相关研究成为新的研究热点。针对基于多层网络的研究还刚刚起步,相关研究还比较少,本文研究了多层网络中的连通k-核社区发现和搜索问题。本文提出了一种新的模型:连通k-核,用于建模多层网络中的k-核社区。本文主要研究三类问题:连通k-核社区发现问题,最大连通k-核社区发现问题和连通k-核社区搜索问题。(1)连通k-核社区发现问题指的是给定多层网络G和向量k,找到多层网络上所有连通k-核。本文提出了一种近似线性的算法,用于发现多层网络G中的所有连通k-核。(2)最大连通k-核社区发现问题是指找出多层网络上所有最大连通k-核。最大连通k-核是图中所有连通k-核中度数阈值k最大的连通k-核。对于多层网络的特殊情况双层网络,本文提出了最大连通k-核社区发现的自底向上和自顶向下的算法,并在最后提出了一种高效的二分搜索算法。对于一般的多层网络,本文提出了基于宽度优先搜索策略的多层最大连通k-核社区发现的高效算法。(3)连通k-核社区搜索问题是找出图中包含给定顶点集合的连通k-核的问题。在多层网络中,本文设计了高效的索引结构来查找包含一组查询顶点的连通k-核。基于所提出的索引结构,本文给出了高效的查询处理算法和多项式时间索引构造算法。本文在包括引用网络,推荐网络,地理社交网络,社交网络等多种领域的大型公开真实数据集对本文所提出的算法性能和有效性进行了评估。同时,通过公开的满足典型的社会网络的模式的随机图生成器合成了大型合成数据集,对算法的性能和可扩展性进行了评估。本文的实验结果证实了本文提出的算法在各个场景下均具有良好的性能,在数据集规模增加时,算法仍然具有良好的可扩展性和鲁棒性,不会发生时间开销不可接受的情况。同时,在Gowalla[7]数据集上进行的与最稠密连通子图[28]进行比较的案例分析证实了本文提出的连通k-核模型具有良好的性质。连通k-核中各个顶点均具有较高度数,不会出现度数较低的离群点,能够更好地表示网络中具有内聚属性的社区。