网络科学是研究现实世界中诸多复杂系统的有力工具,其中节点表示复杂系统的对象或者实体,边表示不同对象之间的关系。当前大部分工作仅针对由单一类型对象及其关系构成的复杂网络,然而现实世界中的许多复杂系统是由多种类型对象和多种类型关系构成的。这种由不同类型对象及其关系构成的信息网络称为异质信息网络。本文主要围绕异质信息网络中特定类型的对象团体形成问题展开,包括:(1)异质信息网络中同类型对象的相似性度量问题;(2)由专家、技能、项目构成的异质信息网络中收益最大化团队形成问题;(3)由用户和活动构成的异质信息网络中社会活动团体形成问题。解决上述三类问题的已有方法均存在一定的局限性。关于异质信息网络上的相似性度量问题,已有度量方法依赖于用户指定的元路径或者元结构。虽然指定元路径或者元结构可以为用户提供个性化的服务(具有特定语义关系的相似性度量),但也会导致所得到的相似性对输入的不同元路径或者元结构较为敏感。此外,让一个非本领域专家的用户指定元路径或者元结构是相对困难的。关于专家技能项目异质信息网络上的收益最大化团队形成问题,已有算法所形成的团队可能包含冗余专家,而且它们无法为每个被选择的项目指定具体负责的团队,从而也就无法考虑专家所参与项目的个数。关于用户活动异质信息网络上的社会活动团体形成问题,已有的社会活动团体形成问题没有考虑为用户提供多样化的活动选择。本文的主要贡献可以概括为:(1)本文为异质信息网络设计了两种纲要结构:分层元结构(Stratified MetaStructure,SMS)和循环元结构(Recurrent Meta-Structure,RecurMS)。SMS与RecurMS均可以自动构建而无需用户参与,并且包含了大量的元路径或者元结构。对于SMS,本文定义了元结构的通勤矩阵,并通过将不同元路径或者元结构的通勤矩阵按照不同权重组合,从而形成SMS的通勤矩阵。基于分层元结构的相似性度量SMSS便利用SMS的通勤矩阵进行定义。对于RecurMS,为了将不同对象类型解耦,本文提出一种将RecurMS分解为若干循环元路径和循环元树的方法,并分别定义了循环元路径和循环元树的通勤矩阵。为了评估不同循环元路径和循环元树的重要性,本文提出两种加权策略:局部加权策略和全局加权策略。基于循环元结构的相似性度量RMSS便可通过将循环元路径与循环元树的通勤矩阵按照不同的权重组合在一起进行定义。需要注意的是,RMSS可以通过调节不同循环元路和循环元树的权重,从而为用户提供个性化服务。(2)本文分别研究了在不同约束条件下(无冗余、明确的项目团队对应关系、参与约束等)的三类子问题。针对无冗余的收益最大化团队形成问题,本文利用贪心策略提出一种删除冗余专家的方法Eliminate。给定一个团队以及被该团队覆盖的项目集合,Eliminate依次选择对当前项目集合具有最大覆盖率的专家,直到该项目集合所要求的技能都被覆盖为止。删除冗余专家后,团队成本必然下降。此时,我们可以将一些额外的专家加入到团队,从而使得团队能完成更多的项目。本文提出了团队增强算法Augment。该算法依次从尚未被选中的项目集合中选择具有最大选择度值的项目,并将其对应的无冗余团队加入到当前团队中。针对明确项目团队对应关系的收益最大化团队形成问题,本文改进了现有团队形成问题的定义,明确地为每个项目指定具体负责它的团队,并提出基于投票策略和贪婪策略的团队形成算法Influence。该算法以全局项目团队映射作为输入,依次删除影响力最小的专家,直到团队成本低于预算。明确了项目与团队的对应关系后,本文进一步分析了团队中专家的负载情况,发现专家参与的项目个数差距很大,也就是专家工作负载不均。本文提出了考虑参与约束的团队形成问题,并提出项目优先算法(Project-First Algorithm,ProjectFirst)算法和专家剔除算法(Expert-Removing Algorithm,ERA)算法。这两个算法均根据项目收益与负责该项目的无冗余团队的成本之比作为选择标准。(3)本文提出一个为用户提供多样化活动选择的社会活动团体形成方案。该方案明确地区分了用户对活动的主观偏好和客观偏好。用户对活动的主观偏好可以通过迭代方法进行估计,客观偏好可以利用期望最大化(Expectation Maximization,EM)算法进行估计。利用这些客观偏好,可以构建由用户与活动构成的加权二部图,然后利用整数规划对社会活动团体形成方案进行建模。该整数规划可以松弛为线性规划问题。由于线性规划问题可能没有可行解,本文在适当违背软约束的前提下提出了可以为用户提供多样化选择的社会活动团体形成算法(Algorithm for Forming Social Activity Group,AFSAG)算法,从而保证始终能得到一个社会活动团体形成方案。