基于粗糙逻辑的隐含路径研究
时间：2022-06-01 03:36:11
摘 要：针对目前社交网络的研究多是基于内部成员之间的直接关系的研究。突破用图来定义社交网络的方式，提出了社交近似空间的概念，并通过发掘社交子空间的不精确路径定义了隐含路径，从而探索了一种针对社交网络的新的研究方法。
中图分类号：TP3-0 文献标识码：A 文章编号：16727800（2013）002002103
0 引言
网络与信息技术的快速发展，使得网络成为人们生活工作中必不可少的部分。网络设计是以电子邮件替代实体书信作为起始点的，进而演化出BBS、开心网络等，呈现出虚拟化特征。在网络社交演变的这个过程中，个人形象由实体转化为网络虚拟形象，也就促使了社交网络的诞生，也就使得人与人之间表现出联系扩大化、成本降低化的特点。现在流行的社交网络认为是网络+社交，即通过网络这一载体把人们连接起来形成具有某一特点的虚拟团体。
社交网络最初的理论基础来源于六度分隔理论（也称小世界理论），该理论是由美国社会心理学家米尔格兰姆（Stanley Milgram）提出的，并通过连锁信件进行了实验证明。分析这个早期实验发现，人与人之间的通信、交流的传播状态一般可以分成两种，一种是直接认识，另一种是两个人通过某些中介人间接认识。本文基于这个思想，将波兰数学家Pawlak的粗糙集引入到社交网络中，通过逻辑方式建立了社交近似空间，并提出该空间内子空间关联路径的概念。
1 社交网络与链接挖掘
社交网络是基于现实社会中人与人之间的信任关系而建立起来的，典型的小世界理论网络，它提供了一个可以维系社会关系的网络平台。从这点上看，认为社交网络是建立在结点和关系的基础上的，结点可以是人也可以是机构、组织、企业等等， 关系可以是组合的方式、交流的方式等等。目前，传统网络的表示形式大多是通过图来描述的，一般都将社交网络表示成加权图G=（V，E，W），V是成员v组成的结点集合，E是关系成员e组成的关系集合，e（vi，vj）则表示成员vi和vj存在联系。社交网络中的W通常是代表关系程度w（e）组成的集合，用来表示两个成员之间关系的强弱程度。
社交网络是基于信任关系建立起来的，在某种程度上反映了真实社会中的结构。那么可以用简单的例子对实际社会结构中的信息传播途径进行一个说明。首先社会由很多人构成，其次人又由某种联系构成很多子群体，再次是人们交往认识的途径不外乎分为直接和间接。信息的传递和认识途径十分相似，所以先对认识途径做个进一步的分析。
直接关系是最简单的关系。例如，a与b直接认识，那么可以将这种关系定义为S，那么用序偶对∈S就可以表示两者之间的直接关系。但还有一些情况是两个人之间从表面上来说没有直接关系，通过一个或者一系列中间人才能认识的。列举一个最简单的例子：a认识c而c又认识b，那么通过c的介绍a就可以认识b，即可表示为，因为存在∈S，∈S，则有∈S，显然它不同于两者直接存在关系，所以认为是一种间接联系。这种间接联系可以通过精确路径的方式描述出来，V是结点的集合，E是关系的集合，且EV×V。存在va，v1，v2，…，vn，vb∈V并且有∈E，∈E，…，∈E，∈E，则，…，就可以称作va到vb关于E的精确路径。精确路径其实就是每个序偶都能被关系E精确描述，相邻序偶首尾元素均为同一个元素的一条关系链。通过精确路径就可以将va和vb这两个不相邻结点间接联系起来。
但是实际中还存在着一种不容易看出来的联系，它也是一种间接的联系，但是却是潜在的，无法用精确路径进行描述的。也正是基于以上对社交网络结构的分析，和隐含路径这个事实的存在，提出了一个下面这种新的表示社交网络结构的方法。
2 隐含路径的提出与分析
下面在社交近似空间M`=（V，R，E）上建立一个联系路径的概念，用来表示社交网络中结点之间联系。在提出模型是基于等价关系分类的基础上，所以认同为同一等价类中结点间的联系是不可区分强弱程度的。为便于隐含路径的定义，首先将二元关系进行粗糙化。
定义1 设M`=（V，R，E）为近似社交空间，V/R=＼[v1＼]，＼[v2＼]，…，＼[vm＼]为R针对V所构成的社交子空间划分，E为社交近似空间M`=（V，R，E）上的二元关系。令E*=|＼[vi＼]，＼[vj＼]∈V/R且∈E}，称E*为E在社交近似空间M`=（V，R，E）上的粗糙关系。
显然，关系E粗糙化后形成的关系E*是关于社交近似子空间之间的关系，即E*是用来表示社交网络中的子群体之间的关系。在此基础上，来对隐含路径进行定义。
定义2 设M`=（V，R，E）为社交近似空间，V/R＼[v1＼]，＼[v2＼]，…，＼[vm＼] 为R针对V所构成的划分，E为社交近似空间M`=（V，R，E）上的二元关系。已知存在a∈＼[vk＼]和b∈＼[vi＼]，＼[vk＼]≠＼[vi＼]，（k=1，2，…，m，l=1，2，…，m）则从a到b存在着关于E*的路径，，…， ，其中i，j=1，2，…，m且i≠j≠k， i≠j≠l，则有vi1，vi2∈＼[vi＼]（i=1，2，…，m），vj1，vj2∈＼[vj＼]（i=1，2，…，m），则将，，…，称为近似空间M`=（V，R，E）上从a到b关于E的隐含路径，记为τ。其中的序偶称为粗糙边，a和b分别称为始点和终点。
分析以上定义，看到关于两结点间隐含路径显然不同于第二部分中提到的直接联系和间接联系，它正好可以反映出社交网络中存在的那种隐含的间接联系。同时还可以从以下命题得出隐含路径和前面提到的两种路径之间的内在关联。
命题1 隐含路径τ：，，…， ，是社交近似空间M`=（V，R，E）上关于E的直接路径的充分必要条件是有a∈＼[vk＼]和b∈＼[vl＼]，使得∈E。
也就是说，当a和b的路径中间没有任何中介点时，就认为a、b有直接关系，显然它们之间就具有直接路径。
命题2 隐含路径τ：，，…，是社交近似空间M`=（V，R，E）上关于E间接路径的充分必要条件是vi1=vi2∈＼[vi＼]（i=1，2，…，m），vj1=vj2∈＼[vj＼]（i=1，2，…，m）。
从以上命题可以看出，当a到b的隐含路径定义中相邻序偶首尾元素为同一个元素时，就形成了一个精确非直接路径，为和隐含路径区分开来，就称之为间接路径。回想社交网络的小世界理论的实验，也可以将a到b的隐含路径扩展到从一个群体出发到目标个体的隐含路径，此时可以将起点a扩展为＼[a＼]（a的等价类）。
从以上定义可以得到关于a到b关于E的隐含路径并不唯一，因此可以得到一个关于所有隐含路径Γ=∪τ的集合，其中，{τ}表示τ上隐含路径τ上出现的结点，{Γ}表示所有隐含路径中结点的集合。利用这个概念提出了对隐含路径τ的一种度量方法。在此首先引入Pawlak上近似概念，对于近似空间M=（U，R），如果有XU，则X在M=（U，R）上的上近似为：R*（X）= ∪{＼[ai＼]|＼[ai＼]}∈U/R^＼[ai＼]∩X≠}。
定义3 设E为社交近似空间M`=（V，R，E）上的二元关系，a，b∈U，τ是从a到b关于E的一条隐含路径，Г是所有隐含路径的集合。则关于{τ}，{Г}的上近似定义如下：R*（{τ}）=∪{vi|vi∈{Г}^＼[vi＼]∩{τ}≠}
R*（{Г}）=∪{vi|vi∈V^＼[vi＼]∩{Г}≠} 定义4设E为社交近似空间M`=（V，R，E）上的二元关系，a，b∈U，τ是从a到b关于E的一条隐含路径，Г是所有隐含路径的集合。|R*（{τ}）|和|R*（{Г}）|分别表示R*（{τ}）和R*（{Г}）的个数，令：μ（τ）=|R*（{τ}）|R*（{Г}） 称μ（τ）为隐含路径τ在社交近似空间M`（V，R，E）中的Г跨度。
μ（τ）是一种近似度量，反映了固定的起始点形成的隐含路径总集合中，τ在Г中经历的等价类数量。将社交子空间的内部关系看成是对等的，那么τ跨越的Г等价类数量越少，说明这个隐含路径的长度越短。
3 粗糙网络在隐含路径稳定性预测
建立了社交近似空间就是为了发掘隐含路径的存在。从定义的过程看出，隐含路径的发现就是在社交近似空间里，提取出关于固定起点（固定群体）到固定终点的隐含路径的粗糙网络。隐含路径的构成是通过先建立粗糙关系E*的关系矩阵ME*=（θij）θij=1 ∈E*
0 E* ME*通过中的归纳构造法可以得到E*的路径矩阵WE*=（σij）。对于社交近似空间M`=（V，R，E），E其上的二元关系，且有V/R=＼[v1＼]，＼[v2＼]，…，＼[vm＼]，E*为E上的粗糙关系，ME*是其关系矩阵，WE*是其路径矩阵，则对a，b∈∈，如果a∈＼[vk＼]且b∈＼[vl＼]，那么当WE*中的元素σkl=1是就表明有一条从a到b的隐含路径存在。然后就可以通过计算每条隐含路径τ的Г跨度来确定那条隐含路径是最短的。
下面举例来说明社交近似空间和隐含路径的应用。
目前大城市中，商品住宅小区中物业人员为方便社区人员的管理和联系，会建立一个虚拟社区，其中那么可以将该社区的所有居民形成了一个集合Г，通过家人关系R可以得一个V/R划分，即V/R{＼[v1＼]，＼[v2＼]，…，＼[vn＼]}说明小区有n户人家。现在＼[v1＼]家庭的孩子小a因为某种原因想要传递一份文件给家庭＼[vb＼]的孩子小b，但是他们并不直接认识显然只能通过社区其他的家庭人员做中间人才能完成。其中一条路径就是小a可以通过自己同社区的同学、朋友建立关系来认识小b，另外他还可以通过他的父母的关系联系其他家庭从而联系到小b，这样显然形成了a和b的间接或者潜在的路径，而实际情况一定是通过最短的家庭数可以最快的达到小a的目的。
4 结语
通过以上的一系列的定义、命题，利用粗糙逻辑的方法建立起一个社交网络的空间概念，又在该空间上建立了不可区分类别间的隐含路径概念。本文建立的社交网络是建立在等价关系划分的基础上的，表示的是子空间内部具有的等价信任关系的特征，显然这是一种有限制的、特殊的网络划分形式，因此是有局限性的。同时仅对潜在的路径的度量和判定做了初步的研究，所以下一步的研究方向一方面是对隐含路径进行进一步深入。另一方面，还可以建立具有相容关系的社交空间，从而适应更多的复杂社会关系。虽然还有很多的问题需要进一步研究，但是利用粗糙逻辑的方法为社交网络的研究又开辟了一个新的拓展空间。
参考文献：
＼[1＼] L SORENSEN. User managed trust in social networkingcomparing facebook， myspace and linkedin＼[A＼]. Proceedings of the 2009 1st International Conference on Wireless Communication， Vehicular Technology， Information Theory and Aerospace and Electronic Systems Technology＼[C＼].Piscataway：IEEE Computer Society Press，2009.
＼[2＼] 闫林.近似空间上粗糙路径的研究及应用＼[J＼].计算机工程与应用，2005（21）.
＼[3＼] KOLMAN B， BUSBY R C， ROSS S C. Discrete Mathematical Structures＼[M＼]. New Jersey： PrenticeHall， Inc，2001.
＼[4＼] 何童，卢昌荆，史开泉，粗糙图与它的结构＼[J＼].山东大学学报：理学版，2006（6）.
＼[5＼] Lü L，ZHOU T. Link prediction in weighted networks： the role of weak ties＼[J＼]. Euro physics Letters，2010（1）.
＼[6＼] 龙毅宏，潘丹.基于模糊理论的间接推荐信任传递研究＼[J＼].武汉理工大学学报，2009（16）.
＼[7＼] 东昱晓，柯庆，吴斌.基于节点相似性的链接预测＼[J＼].计算机科学，2011（7）.
