计算机领域的社交网络解析

来源: 开云全站app
2012/12/24 18:53:01
社会学家以前可能一次只能研究几千个人,但现在有了社交网络,我们可以去研究几百万个体之间的互动

分享到: 新浪微博 腾讯微博
本文关键字: 计算机 社交网络

社会学家以前可能一次只能研究几千个人,但现在有了社交网络,我们可以去研究几百万个体之间的互动。下面为大家展示一些你们可以做的事情。一个非常重要的研究方向就是,弄清楚这些社区是如何形成和演进的。早期这个领域的工作,叫做平均切割(Mean Cut)。他们会把这个图分成一段一段,就是任何一个点都有一个平均距离的连接,他们以小图的方式来解决。事实上,我们绝不希望去研究一个由一百万个点组成的大图,然后分成各有五十万小点的小图,那么我们怎么做呢?早期的研究要假设出这样的一个社区:在这个社区的人,他们在社区内和人之间的联系,之间联系的距离比圈外的人的线要短。但其实并不是这样的。作为个体,我在社区外有很多要连接的人,我们知道在这个社区之外存在数以亿计的人,所以很有可能,我和这个社区之外的一种连接的路程其实更短,要比社区之内更短,因为我们可以看到这个社区之外存在的人的数量更多的,这就是为什么这个概率更大。同时,我们还可以问一下,我都存在于哪些社区?因为我同时存在于多个社区。所以要做的基础性工作就是,我刚才谈到的如何找到社区。下面我举个例子。

这张图代表顶点之间的临近性。大家可以看到左上角,每一个顶点都互相连接。但是在社区之间并没有连接,如果有这样的情况的话,你会发现,我们所说的在右边的这样的奇异向量,我们可以看到这些向量,把它们组成一个三维的图,这是一个例子。也就是说,在这个社区中的所有的点,所有的人,都是和一个点连接的。那么,也就是说即使这两点之间,这两个人之间没有直接的联系,但是他们也间接的实现了中心的连接。所以,我们就可以使用K平均来找到这些社区。但是有一个问题,如果这些社区之间出现了重叠,比如说两个社区之间有重叠的话,那么我们就会看到有三个集群,而不是两个。也就是说有两个是在这个象限,在坐标的两个极端点。

所以,我们不是说要进行“行”的奇异向量计算,而是要找到零常规向量。也就是说用这三个矢量,来抽取出一个社区。我们希望找到那个最小的零常规的向量,当然这就是所有的零的一个向量。后来,我们发现了最小的0的向量是NP号的。我们刚才描述的就是如何找到网络的全球结构,这也是我们如何把它应用到一个有一百万,甚至三百万个点的图。我们希望修改这个算法,用于更多的网络。下面有一个实际的例子,展示我们都做了什么:

假设,有三个池塘,他们互相连接,我们把一个圆片扔到了其中一个池塘里。在我们把这个圆片扔进去之后,我们知道这个圆片掉到了哪个池塘里,但是过了一会儿之后,我们不知道它到底落在这个池塘的哪个位置。再过一段时间,就不知道这个圆偏流到哪个池塘了。下面要做的就是进行一个比喻,找到这个奇异的向量,发现发生了什么情况?我们做一个随机的游动,包括它怎么融合起来,它聚合之后会做什么呢。我会采取五个步骤,这些步骤有足够的时间,在五十个大的社区覆盖,但是并没有覆盖到所有的网络。这样做是为什么呢?就是找到一个最近的向量,就是在他的子空间里面,我只需要五步就把这个子空间填满了,这是非常好的办法,就是找到相关的社区。

这里有一些研究,目前做的当中有一个范数的向量,并不是指标性的向量,跟零一样,需要一个门限值,就像这样的向量的情况,你可以决定什么时候切割这个限值,找到你的社区。实际上你并不一定想要在这样的子空间里找到这个向量。你最不愿意做的就是找到跟这个子空间最近的一个向量。我们做什么呢?我们可以把一个Y的范数最小化,再加上一个恒定的量,再加上子空间的角度,如果这是恒定无限的,你可以在这个子空间里找到一个向量。如果变成0的话,一个范数的向量,你可以找到恒定的答案,得到这样的结果。人们对一些研究问题非常感兴趣,就是随机的长度多长,需要填充的子空间,以及人在几个社区当中。我们需要这样的研究,这些典型例子是好的,在上百个领域做这样的研究,这是你们以后在社区当中也可以做的。

我们跳过一下,其中有一点就是需要了解比较大的图。这张大图,我在上学的时候,差不多有15个顶点,可以在这个纸上画出来,有上10页的顶点。然后这些小图也是很重要的,其中在你的图上可以随机的擦除掉其中一个顶和边,它不会影响到你的属性。有一系列的大图,可以提供定例的图例,还有一些图形,就是选择N个顶点,然后再将这些潜在的边缘放到里面,这是非常好的理论,证明了很多的定理,还有很多的书籍是关于这个图的。

这是现实中美联航的航路图,在北美地区的。这个图里面有很多城市的顶点,城市之间有直航的边,你可以看一下分布的情况。通过双范数,生成这些图的模型。我们从一些小的顶和边添加做起,在里面加了一些顶和边,我们需要一些规则,如何联系所有新加的边,叫做偏好性的连接,这当然是一种随机的,一定的概率到某种程度上,你可以得到一个叫做明律的分布。再举个例子,就拿这个图来说。在我们教授课程的时候,经常让学生到外面找一个数据库。他们可以很容易的进行转换,把它变成一张图的数据库。这个数据库是学生拿过来,其中有2073个蛋白质,成为顶,3602个互动,属于边,这个里面再进行计算,把这里面的分量结合起来,然后变成48个独立的顶,这是在其他蛋白里面没有的。其中还有179个对相互之间可以互动的。这都是我们所说的社区大小。

接下来,我们会编写一个计算机程序。但是如何检验这个计算机的程序呢?我们把这个社区大小和社区数量乘在一起,它变成了什么呢?在合成的成分当中,我们只是得到了899个蛋白质,还我们缺少1851个。是我这个程序有错误了吗?我们运行的时间长一些,并没有达到1000个。进一步进行推算,我们有很大的数量,1851个,他们找到的缺少的部分。也许你们很奇怪,这张图怎么有这么大的组成部分和分量呢?这样的大图,每一个现实的图当中,都有这样的内容,这都是非常重要的。你们要能够理解它怎么形成的。在你的数据库里面可以做这样的实验,可以有不同的结果。

责编:chrislee2012
vsharing 微信扫一扫实时了解行业动态
portalart 微信扫一扫分享本文给好友
著作权声明:kaiyun体育官方人口 文章著作权分属kaiyun体育官方人口 、网友和合作伙伴,部分非原创文章作者信息可能有所缺失,如需补充或修改请与我们联系,工作人员会在1个工作日内配合处理。
最新专题
网络安全热点透析

随着移动互联、大数据、云计算、物联网等技术的日益发展,在这些热点技术为个人生活带来便利的同时,也为企业发展..

数据安全医药行业解决方案

采用身份鉴别、访问控制、数据加密以及权限控制等多种安全防护技术手段,保障数据库中医药数据只能被合法用户合规..

    畅享
    首页
    返回
    顶部
    ×
    畅享IT
      信息化规划
      IT总包
      供应商选型
      IT监理
      开发维护外包
      评估维权
    客服电话
    400-698-9918
    Baidu
    map