社会网络(Social Network)是指社会个体成员之间通过社会关系结成的网络体系。近年来,随着信息技术的发展,在线社交和微博等新兴社会网络应用获得了快速发展,为人类交互、知识共享、信息传播提供了完善的通信平台,也对人们的日常生活和行为方式产生了显著的影响,因此,在当今这个在线社交的时代,对社会网络研究更具有重要的理论价值和实际价值。对在线社交网络的分析与挖掘也存在着巨大的挑战。社会网络与一般信息网络相比,有其独特的特性。例如,社会网络中的个体和群体在行为上体现出了强烈的社会性特征,对其他节点和网络上下文具有强烈的依赖性;在线社会网络时代多样的应用类型带来了多样的网络属性,对个体和群体可以从各个侧面进行描述,具有多维性;个体在网络中的行为与网络拓扑结构相互影响,内容和结构具有明显的互动关联性;个体在网络上发表信息内容,生成相互关系,演化性也是社会网络中的重要属性。本文在分析了相关工作的基础上,主要针对社会性、多维度、关联性、演化性四个特征分别进行了研究,主要研究内容和成果包括:(1)在社会网络的社会性分析方面,本文重点研究了节点间的相互依赖和支持现象。本文通过分析网络链接结构与个体影响力的相互关系,将社会网络中个体间的依赖关系从一般社会关系中抽取出来,建立了一种依赖网络模型,将一般社会网络结构转化为依赖关系网。在此基础上,结合依赖距离的最近邻和k近邻方法,给出了一种类似于“投票”的个体支持力计算方法。支持力可以用来对社会网络上的个体进行排名,与其他基于链接关系的节点重要性度量不同的是,支持力度量则更侧重于个体对于其他网络群体的贡献,体现的是网络对个体的“倚重”程度。此外,我们还将依赖模型扩展到社会网络的社团发现技术上来。通过依赖性模型,可以发现成员间紧密依赖、互不可分的网络群体,即依赖型社团。本文我们还给出了依赖型社团的定义和发现方法,以及多个衡量社团质量的标准。(2)在多维性方面,本文重点研究多属性约束的社团分析和挖掘方法。本文在加权图的基础上,提出了一种基于最近邻关系和准完全图的社团定义,目标是识别网络中,既满足规模要求、又连接紧密的社团。基于这个模型,我们分析了社团紧密度和社团成员规模的相互约束条件,给出了一种基于多准则约束的挖掘方法。该算法不但具有在网络的不同边密度地区识别社团的能力,而且在结果上能够同时体现出社团规模和紧密度的折衷关系。我们分析了多种约束条件对社团搜索的影响,并利用约束间的相互制约关系,给出了高效的局部搜索算法和剪枝策略。(3)在内容和结构关联性方面,本文重点研究层次化的特征蔟抽取方法。本文将在扭曲空间中的社会网络结构,通过层次式提取,映射到空间曲面上来,形成一种类似于等高线地形图的密度分布层次结构,旨在分析社会网络上的特征群体在内容上的独特性。本文给出了一种基于网络拓扑结构的标注密度估计方法,即将网络上的离散的标注信息,通过一种类似于疾病传播的模型,抽象为标注密度函数。并通过在层次结构中不同粒度的簇中的聚合计算结果,估计标注在链接结构中各处的特征指标。本文设计了特征簇的挖掘算法,即在抽取网络层次结构的同时,通过估计各部分的特征函数的上下界,达到了自底向上的剪枝效果,从而实现了高效精确计算特征簇的算法。(4)在演化性方面,本文重点研究个体社会影响力的早期预测技术。本文首先将话题的传播趋势模型化为一组带有时间标注的序列,将当前已经发生的事件作为训练样本,通过对当前时刻之前的已发生的事实数据进行训练,从而生成分类和预测规则,以达到对当前时间之后的话题趋势进行预测分析的目标。本文综合社会网络内容的演化性和网络固有结构特征两个方面,设计了时间序列模型,并给出了基于结构和内容相似性的时间序列匹配方法。通过对新近发生的事实与之前的预测结果进行对比,从而达到对分类器进行评估,调优或重新训练的目标。综上所述,本文针对社会网络的社会性、多维度、关联性、演化性四个特征,研究了社会网络的个体排名、社团发现、特征抽取和趋势预测等关键技术,对于社会网络的分析和挖掘工作具有重要的理论意义和应用价值。