智商情商网熵田园分享 http://blog.sciencenet.cn/u/Liweigang 数字之美,美于形式,更在内涵。

博文

微博de故事:关系寓意下的邻接矩阵 精选

已有 8797 次阅读 2013-1-4 08:03 |个人分类:社交网络|系统分类:科研笔记| 关系, 微博, 邻接矩阵, 微博de故事, 在线社交网络

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

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

   在人工智能遗传基因的影响下,粉丝矩阵-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次连乘, Ak = A A A。如果两个节点(u, v) 间的连接赋予权重为w(u, v), 如果 (u, v)  ϵ E; 否则, w(u, v) = 0w(u, v)可定义为距离、成本或效益通过计算Ak,可以得出两点间最优k 段路经,如果存在这些路径的话。

 

2粉丝矩阵(RCAM)的定义

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

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


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

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


3粉丝矩阵的计算实例

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

 

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


   2表达一简单社交网络,其中各种关系均相对于用户v:用户u关注vx,用户v关注wx,用户x关注uv。在此基础上,图3(a)  列出的粉丝矩阵Ain的具体表达,图3 (b) 列出的关注矩阵Aout的具体表达。

 

                    图 3.(a) 粉丝矩阵Ain        (b) 关注矩阵Aout.

   从图3 (a) 粉丝矩阵Ain第一行,可以表达/查询用户uvx的粉丝的信息。从图3 (b)关注矩阵Aout第二行,可以表达/查询用户vux关注的信息。    

   当需要查询朋友的朋友相关信息时,粉丝矩阵的两阶运算 Ain2便派上用场。从图 4 可看出,用户u的朋友的朋友是 vv的朋友的朋友是 ux;等等。

 

 

4. 两阶粉丝矩阵的运算示例: Ain2.

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

 

 

5 关注人的粉丝的计算: AinAout.


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

 

   开发逻辑模型对在线社交网络机制研究是一新趋势,粉丝模型[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] 李伟钢,微博的转发哲学(),  科学网博客,2012http://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.

  [4] J.D. Foley, A. Dam, S.K. Feiner and J.F.Hughes. Computer Graphics: Principles and Practice. Second Edition. 1996.

   [5] 李伟钢,微博de故事:物理学者对计算机科学同行的批评,科学网博客,2013http://blog.sciencenet.cn/blog-652078-648754.html 

    [6] Li WEIGANG, ZHENG Jianya, Liu Yang, Retweeting Prediction Using Relationship Committed Adjacency Matrix In: BraSNAM - II Brazilian Workshop on Social Network Analysis and Mining, 2013, Maceio, Proceedings of Conference of Brazilian Computer Society, SBC 2013,  pp.1561 - 1572, 2013.



 


https://wap.sciencenet.cn/blog-652078-649347.html

上一篇:微博de故事:物理学者对计算机科学同行的批评
下一篇:巴西人才计划与科研管理的技术支持
收藏 IP: 164.41.210.*| 热度|

28 应行仁 陆俊茜 蔡庆华 刘艳红 刘锋 杨宁 李学宽 陈冬生 武夷山 林涛 赵新超 王海辉 曹聪 马剑 边一 唐朝生 赵美娣 谢力 王春艳 杨学祥 蔣勁松 庄世宇 苏德辰 刘桂秋 翟自洋 李天成 crossludo ywh222

该博文允许注册用户评论 请点击登录 评论 (10 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-7-22 09:59

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部