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

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

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

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

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

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

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

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

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

微信扫一扫实时了解行业动态

微信扫一扫分享本文给好友