2.2 网络科学

2.2.1 图和网络

自然界和人类社会中许多事物以及事物之间的联系，都可以用点和线连接起来的图形来抽象和描述。图和网络是运用十分广泛的研究和建模工具。1736年，数学家欧拉运用图论解决了哥尼斯堡七桥问题。如今图论已广泛应用于计算机、物理、化学、控制论等领域，同时，图与网络理论也广泛应用于管理科学、经济科学等领域，用于解决决策、优化等问题。在近年来的研究热点领域（如大数据、人工智能等）中，很多理论基础也有着图论的影子。

图是由节点和边构成的集合。图可以分为无向图和有向图。

无向图是一个无序二元组(V,E)，记为G=(V,E)，其中，V=(v1,v2,…vp)，是p个点的集合，简称点集；E=(e1,e2,…eq)，是q条边的集合，简称边集合，并且eij是一个无序的二元组，记为eij=[vi,vj]=[vj,vi]，vi,vj∈V。由点和边组成的图称为无向图。在无向图中，主要有环、链、圈、多重边等结构，以及点的度等参数。

有向图是一个有序二元组(V,A)，记为D=(V,A)，其中，V=(v1,v2,…vp)，是p个点的集合，简称点集；A=(a1,a2,…aq)是q条边的集合，简称边集合，并且aij是一个有序的二元组，记为aij=[vi,vj]≠[vj,vi]，vi,vj∈V,aij是以vi为始点、vj为终点的弧。由点和弧组成的图称为有向图。在有向图中，包括有向边、出度、入度等参数。

设G=(V,E)是一个无向图，如果顶点集V可分割为两个互不相交的子集(A,B)，并且图中的每条边所关联的两个顶点分别属于这两个不同的子集，则称图G为一个二分图。

在实际研究中，有时需要在图中赋予边一定的数量指标，称之为“权”，比如在交通网络中的两个点之间的距离、时间、费用等，在资金网络中的资金转移量等。通常把赋权的图称为网络。与无向图和有向图相对应，网络也可以分为无向网络和有向网络。

在计算机上进行建模与计算的过程中，为了便于计算与存储，可以用矩阵来表示图和网络。在后面，为了方便，我们主要用网络的概念进行阐述。

自然界和我们生活的复杂社会都可以抽象为节点和边组成的网络。针对复杂的自然、社会现象，建立各种类型的网络模型进行抽象、计算等研究，已经成为学术界和业界关注的热点和前沿研究领域。从复杂性的角度来说，网络为研究复杂性提供了全新的视角，极大地改变了人们对复杂外部世界的认识，推动了统计物理、非线性动力学、应用数学、信息工程、社会学、生物学、管理学等多学科的交叉与发展。

2.2.2 复杂网络

复杂网络理论将复杂系统抽象为节点和节点之间连接的复杂网络，节点和连接的特性可以用“度”“权重”“强度”等来刻画，是复杂网络推荐算法的理论基础。复杂网络理论是一种抓住本质的抽象，在多个领域取得了很有意义的成果。推荐系统领域常用到的复杂网络的概念包括度、度分布、聚集系数、最短路径以及小世界网络等。

（1）度与度分布

度（degree）：节点的度是指和节点直接相连的边的数目。在有向图中，节点的入度是指指向节点的边的数目，节点的出度是指从该节点出发的边的数目。

度分布（degree distribution）：标识一个特定度与这个特定度的节点数之间的关系，其定义为在指定的图中任取一个节点，度正好为A的比率，即度为A的节点个数占节点总数的比例。度分布函数表明了系统的统计特性。

了解数据集的度分布有助于设计合理而高效的推荐算法，使算法更加符合用户的需求。比如对于呈长尾分布的数据集，在构建推荐算法时，应该注重推荐的覆盖率问题，推荐算法应使尽可能多的项目出现在对其感兴趣的用户的推荐列表中。以使用UGC标签系统的数据集为例，UGC标签系统是很多Web 2.0网站的必要组成部分，使用UGC标签系统的代表网站有豆瓣（书和电影评论网站）、Delicious（美味标签网站）、Lastfm（音乐网站）、CiteULike（论文标签网站）、Hulu（视频网站）等。

（2）聚集系数

聚集系数主要描述网络的密集程度。

计算方法：如果节点n与kn个节点相连，假设kn个节点相互连接，则存在kn(kn-1)/2条边，而这些节点之间实际上存在fn条边，那么节点n的聚集系数为：

全连通图的聚集系数为1，完全随机网络的聚集系数为1/N。大部分真实网络的聚集系数在1/N与1之间。

（3）最短路径与小世界网络

复杂网络任意两个节点之间都存在着至少一条连接通路（孤立点除外），其中经过节点数最少的一条通路称为两点之间的最短路径。将全部的最短路径加和平均后得到网络的平均最短路径。

设G=(V,E)是一个联通图，其中V和E分别为节点和边的集合，任意两个节点vi和vj之间的最短路径为lij，则G=(V,E)的平均最短路径为，其中n为最短路径数量。

在社交电子商务等基于社交网络的应用系统中，利用社交关系推荐用户感兴趣的产品或服务，是推荐系统的重要组成部分。比如Dopplr的旅游伙伴、Facebook的新闻反馈以及LinkedIn的朋友推荐等。

美国著名社会心理学家Milgram于20世纪60年代提出了“小世界网络效应”（六度空间理论），指出：任何两个素不相识的人，通过一定的方式，总能够产生必然联系或关系。小世界网络理论在社交网络朋友推荐中广泛使用。根据小世界网络理论，可以认为在线社交网络的平均最短路径较小，聚集系数较大。基于此，挖掘网络所有路径结构的全局朋友推荐算法可以改进为遍历有限长度路径的局部朋友推荐算法，因为基于全局的朋友推荐算法成本高、复杂度大、效率低，而在聚集系数较大的网络中，基于局部特性的推荐算法的效果有时甚至会超过一些更复杂的全局算法。

2.2.3 超网络

随着互联网、物联网的深度应用，整个社会日益呈现网络化、多样联系的特征。在研究超大规模的网络系统时，会出现物流网络、信息网络、资金网络等相互交织的问题，或网络中的网络。这类网络系统的出现不但提高了运行效率，而且催生出新的生产、经营、消费的方式，但同时也带来了系统运行的复杂性。传统的同质性的网络研究理论方法，有时很难理清这些网络之间的关系。

超网络的概念最早由MIT的Y.Sheffi在研究运输系统时提出。A.Nagurney把高于而又超于现存网络的网络称为“超网络”。

超网络具有以下特征：

（1）网络嵌套着网络，或者网络中包含着网络。

（2）多层特征。例如，互联网的传输协议是多层的，互联网下的金融系统包括物理层、传输层、传统业务层等。层内、层间有连接关系。

（3）多级特征。例如，企业的信息网络有总部、公司、部门等级别。同级、级间有连接关系。

（4）关系的多维特征。例如，在互联网金融业务中，既有信息流，又有资金流的关系。这些多维的关系甚至交叉融合在一起。

（5）多准则特征。例如，在运输网络中选择交通方式时，往往需要综合考虑时间、成本、安全和舒适性等。

（6）整体与个体的冲突。在复杂的网络中，往往个体的最优选择同全局的最优有冲突，需要协调。在信息传播日益发达的网络时代，虽然决策者更容易获得信息，决策依据的信息更多，但由于关系网络的复杂性，全局优化和个体优化之间的冲突问题也更加突出。

超网络的架构为研究网络之间的相互作用和影响提供了理论方法。超网络模型可用来描述和表示网络之间的相互作用和影响。可以利用网络科学、博弈论、变分不等式等进行定量的科学研究。

A.Nagurney主要利用变分不等式来解决网络平衡模型的优化问题。超网络的拓扑结构是超图。另一个主要的研究思路是用超图进行有关的超网络研究。

从超图的角度，可以给出超网络的定义。C.Berge在1970年提出超图的概念，建立了无向超图理论，并将其应用在运筹学的研究中。Estrada认为，凡是可以用超图描述的网络就是超网络。根据超网络的特征，确实有许多超网络难以用一般的网络图描述，需要用超图来描述。

超网络可以看作一类特殊类型的复杂网络。Barabasi等曾提出网络研究的10个主要问题，其中包括“网络的网络”的问题，即研究不同性质网络间的相互作用问题。王志平和王众托从超网络角度系统梳理了理论和应用方面有待解决的问题，包括：超网络的定义、参数和指标研究，超网络的划分和合成研究，超网络的流和权研究，进化变分不等式研究，投影动力系统平衡稳定性研究，风险因素的研究等。近年来，国内众多学者结合我国互联网、电子商务等的发展，对超网络理论及其应用开展了大量深入的研究。

2.2.4 随机游走理论

随机游走（random walk）是指基于过去的表现无法预测将来的发展步骤和方向的运动。简单随机游走是指从某一固定节点开始，下一个游走节点的选择是随机的。通常，随机游走是指简单随机游走。如图2.5所示，假设从A点开始随机游走，经过一步游走之后到达B点，在B点，游走的下一个目标只能是C点或A点，如果游走到C点或A点的概率都为1/2，那么此随机游走是简单随机游走。

基于随机游走的算法被广泛应用于网络研究，如搜索、路由的选择、自适应、无线网络、对等网络以及其他分布式系统。随机游走被广泛使用的原因是其具有局域性、简单性、低负荷和对结构改变的鲁棒性等特点。其中，鲁棒性是非常重要的一个特点。很多网络会由于节点属性的改变、节点间连接的改变或破坏等原因发生结构性改变，此时，基于网络拓扑的算法可能不再使用。随机游走具有对复杂网络改变的鲁棒性，是因为随机游走并不需要事先得到网络的拓扑信息，所有的节点在游走过程中具有同等重要度，节点选择失败的概率可以忽略。

随机游走可被应用于推荐算法的用户或项目相似度度量中。刘建国等提出基于方向性随机游走（Directed Random Walk）的协同过滤推荐算法，研究用户相似度方向（用户i与用户j的相似度为Sij，用户j与用户i的相似度为Sji，该研究认为Sij≠Sji）在推荐中的影响，发现用户相似度与用户的度成反比。Gori等根据用户偏好构建项目相似度网络，赋予每个项目初始用户偏好值，使用简单随机游走对项目进行排序（Item Rank），然后将Top-N项目推荐给用户。但是项目排序算法并不考虑项目分类属性和用户对不同项目类别的偏好，比如，一定数目的用户都对同一部喜剧电影给予较高的评分，这部喜剧电影将与这些用户评价过的其他电影产生连接，随机游走算法会赋予此喜剧电影较前的排序，最后推荐时，该喜剧电影有可能出现在从来不看喜剧电影的用户推荐列表中。因此，在Gori的基础上，张丽艳等认为一个项目在某一类别中受欢迎程度较高，并不代表该项目在所有类别中都有很高的支持度，如果忽略项目在不同类别中的不同受欢迎度，就会导致不准确的推荐，于是引入了一个新的概念——类别排序（Category Rank），用于表示项目在不同类别中的权重，避免明星项目在每个类别中都具有较高的权重。俞琰等根据“小世界”假说，定义了基于局部随机游走的定点相似度，随机游走有限范围内的所有路径，达到局部最优，相比全局随机游走，降低了算法的时间和空间复杂度；对于非周期不可约的图，执行有限次随机游走，当每个节点被游走的概率相对稳定时，取稳定状态概率作为用户之间的相似度，可为用户提供既快速又准确的朋友推荐。

随机游走度量用户相似度的方式较多，最常用的有以下几种。

（1）平均游走步长：从节点i开始到节点j结束，多次游走经过的平均步长。

（2）平均游走时间：从节点i开始到节点j结束，多次游走使用的平均时间。

（3）拉普拉斯矩阵的伪逆（L+）：矩阵L+的组成元素是节点i与j的欧几里得距离，所以L+i，j可以用来表示二者的相似度。

（4）KATZ矩阵：该方法在计算两节点相似度时，既考虑了直接相连的节点，又考虑了间接相连的节点。KATZ矩阵的定义为：K=aA+a1A1+a2A2+······+anAn=（I-aA）-1-I，其中A 为邻接矩阵，a为正衰减因子，表示两节点之间相隔的步长越长，相似度越低。

在简单随机游走基础上，Avin和Krishnamachari于2008年首次提出选择性随机游走。与随机游走相比，选择性随机游走的最大特点是在下一步游走之前，随机选择不止一个而是多个游走目标，并根据一定的策略从中选择最佳游走目标，实现局部最优。此算法使用游走策略来缩短覆盖时间，达到更好的负荷均衡。

选择性随机游走不属于简单随机游走，因为选择策略赋予每个节点的被选概率不同。但在选择下一个游走目标前，产生候选节点集的过程是随机的，这保证了每个节点都有可能进入候选项目集，从而不会有不可达节点。选择性随机游走的过程如图2.6所示。

从B点开始游走，下一步可选择节点为C、D、E，简单随机游走将以相同的概率在C、D、E中随机选择一个节点作为下一步的游走目标，而选择性随机游走则随机选择不止一个节点，组成候选项目集，假设候选集成员为C、D，然后根据一定的选择策略从C、D中选择唯一的一个节点作为下一次游走目标。