邻接矩阵(Adjacency Matrix-AM)伴随着图论，是一个古老的传说。研究各类复杂网络理论时，在高效计算的需求下，用邻接矩阵来表示网络拓扑，是各路大牛高手的首项选择。随着在线社交网络的蓬勃发展和深入研究，尤其是在关系错综复杂的微博平台内，尚未见到贴切的数学或逻辑模型，有效描述用户各种行为和关系，人们越来越感到直接使用邻接矩阵的乏力。

   搞科研也是要个天时地利人和，注重关系意义的逻辑模型呼之欲出？！2012年上半年巴西利亚大学 TransLab 团队推出粉丝模型(Followmodel) [1,2]，在此基础上，考虑到在线网络用户间的多重、多层的复杂关系和大型网络并行计算的潜力，下半年提出关系寓意邻接矩阵概念(Relationship Committed Adjacency Matrix-RCAM) [3]，昵称粉丝矩阵。按照粉丝模型的定义，A_in为粉丝邻接矩阵(FollowerAM)，其转置矩阵就是关注矩阵(Followee AM)，具体表示为A_out = A_in^T。经过多次相乘，A_in^k=A_in A_in … A_in是k-阶粉丝矩阵。如果把n个节点的社交网络用n x n 矩阵A_in表示，则通过A_in²可查询粉丝的粉丝信息; 利用A_inA_out查询关注人的粉丝信息；利用 A_outA_in查询粉丝的关注人信息 …

   在人工智能遗传基因的影响下，粉丝矩阵-RCAM这一华丽转身，竟然使得邻接矩阵风情万种，衍生出说不完的故事来。本文将详细介绍这些关系矩阵的定义和多重组合应用。

1．图和邻接矩阵定义

   为便于描述问题，约以成俗，我们按图论来定义在线社交网络的元素和关系。 四个节点和连接构成一个简单的无向图G= (V, E)，见图 1。节点集V 内有: A, B,C, D ϵ V;  各节点内含一元素，这里指用户名u, v,w  和  x; 节点间形成无向连接集 E: V× V: (A, B), (A, D),(B, C), (B, D) 和(C, D) ϵ E;  用户间可能的关系为: (u, v),(u, x), (v, w), (v,x) 和(w, x)ϵR.

图 1.四节点形成的无向图，网络研究的出发点

   请注意，在此定义里，我们有意分开节点和元素、连接和关系，因为网络内的节点和连接一般是不变的，但在线社交网络的元素和关系随时会发生变化。例如，节点可能会是用户，也可能是微博；关系可能是关注关系，也可能是微博转发关系。

   邻接矩阵A的定义为A(u,v)= 1, 如果 (u, v)  ϵ E; 否则, A(u, v) = 0. 如果图内有n 个节点，则邻接矩阵A的元素为n × n。

   图论进一步告诉我们[4]，k-阶邻接矩阵即矩阵的k次连乘, A^k = A A… A。如果两个节点(u, v) 间的连接赋予权重为w(u, v), 如果 (u, v)  ϵ E; 否则, w(u, v) = 0。w(u, v)可定义为距离、成本或效益。通过计算A^k，可以得出两点间最优k 段路经，如果存在这些路径的话。

2．粉丝矩阵(RCAM)的定义

   参见图 1无向无权重图的基本定义和粉丝模型的概念[1,2]，如果该图表征一社交网络，我们使用粉丝矩阵 (Follower Adjacency Matrix) A_in来表达该网络内各用户间的关注关系, A_in(u, v) = 1, 如果用户 u 关注用户v 且 (u, v) ϵ E; 否则, A_in(u, v) = 0。这里的下标in 和粉丝模型[1,2]的粉丝函数f_in(.) 相对应，表示用户v 的粉丝集(即关注v的所有用户集)。如果该图有n个节点，A_in 具有n × n 个元素。

 粉丝矩阵A_in 描述了相关元素的粉丝关系，通过对该矩阵各行的阅读，查询到有关用户的粉丝信息。粉丝矩阵的转置, A_in^T, 定义为关注矩阵(Followee Adjacency Matrix) A_out = A_in^T。关注矩阵A_out 与粉丝模型中的关注丝函数f_out(.) 相对应，描述了相关元素的关注关系。通过对该矩阵各行的阅读，查询到有关用户的关注人信息。利用互粉关系的对称型，这些信息也可以从上述两个矩阵里分别获取。

   为便于广泛应用，我们通称粉丝矩和关注矩阵为关系寓意邻接矩阵(Relationship CommittedAdjacency Matrix - RCAM)，中文昵称粉丝矩阵。

   在线社交网络用户间的关系并非仅仅是一个层次的关系，例如，朋友的朋友的朋友…，就是多层次关系。有了粉丝矩阵，对这些个关系的描述，则是十分自然的了。我们用A_in^k= A_in A_in … A_in来表达k-阶粉丝关系，A_in^k是粉丝矩阵A_in的k次相乘。 

3．粉丝矩阵的计算实例

   为便于读者体会粉丝矩阵的个中奥妙，本节使用一简单例子，说明粉丝矩阵A_in、A_out、A_in²的具体计算和实际应用。

         图 2.简单在线社交网络中 相对于用户v的粉丝、关注和互粉关系.

   图2表达一简单社交网络，其中各种关系均相对于用户v：用户u关注v和x，用户v关注w和x，用户x关注u和v。在此基础上，图3(a)  列出的粉丝矩阵A_in的具体表达，图3 (b) 列出的关注矩阵A_out的具体表达。

                    图 3.(a) 粉丝矩阵A_in        (b) 关注矩阵A_out.

   从图3 (a) 粉丝矩阵A_in第一行，可以表达/查询用户u是v和x的粉丝的信息。从图3 (b)关注矩阵A_out第二行，可以表达/查询用户v被u和x关注的信息。    

   当需要查询朋友的朋友相关信息时，粉丝矩阵的两阶运算 A_in²便派上用场。从图 4 可看出，用户u的朋友的朋友是 v；v的朋友的朋友是 u和x；等等。

图4. 两阶粉丝矩阵的运算示例: A_in².

   如果需要查询用户的关注人的粉丝，粉丝矩阵与关注矩阵的乘积，A_inA_out可提供相应信息。如图 5 所示，用户u的关注人的粉丝为v 和 x；v的关注人的粉丝为 u,等等。

图 5 关注人的粉丝的计算: A_inA_out.

   通过粉丝矩阵和关注矩阵的的各种组合、各阶计算，我们可以得到对在线社交网络的各类相关信息查询。这些查询对于微博转发预测和信息传播预测都是有着积极的意义。同时，矩阵操作对于开发并行计算资源，意义重大。可以说整个网络各节点的计算都是将是一次性的甚至是同步的。如果说二阶粉丝矩阵A_in²的计算复杂度为O(n³)，当k为有限值时，A_in^k的计算复杂度仍为O(n³)。这一点也是激动人心的，在第一次计算A_in²后，A_in^k将会在各项查询和微博转发预测中多次使用，这正是提出关系承诺邻接矩阵的真正意义之一。

   开发逻辑模型对在线社交网络机制研究是一新趋势，粉丝模型[1,2]和粉丝矩阵[3]是本团队的初步尝试，敬请相关专业同仁相商赐教，以便完善推广。

 《微博de故事》系列博文[5]将继续介绍巴西利亚大学TransLab团队应用粉丝矩阵-RCAM，在微博信息查询、微博转发预测和微博传播等方面逻辑关系模型化的最新研究成果。博文中的一些定义和概念描述可能不够严格和准确，请进一步参照本文正式发表的文献[6]。其它章节将陆续发出，敬请诸位网友指导、稍候。

   参考资料：

   [1] E.Sandes, L. Weigang and A. de Melo. Logical model of relationship for onlinesocial networks and performance optimizing of queries. In Proceedings of WISE,LNCS 7651, pp. 726—736, 2012.

   [2] 李伟钢，微博的转发哲学(下),  科学网博客，2012，http://blog.sciencenet.cn/blog-652078-604604.html

   [3] Li Weigang, Zheng Jianya and Denise LYLi, Querying and Predicting Retweets with Relationship Committed AdjacencyMatrix in Online Social Networks, Resarch report, ThansLab, University of Brasilia, 2012.