google pagerank

  PageRank，网页排名，又称网页级别、Google左侧排名或佩奇排名，是一种由根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Google公司创办人拉里·佩奇（Larry Page）之姓来命名。Google用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学发明了这项技术。
  PageRank通过网络浩瀚的超链接关系来确定一个页面的等级。Google把从A页面到B页面的链接解释为A页面给B页面投票，Google根据投票来源（甚至来源的来源，即链接到A页面的页面）和投票目标的等级来决定新的等级。简单的说，一个高等级的页面可以使其他低等级页面的等级提升。

  PageRank是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和 Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。
  PageRank将对页面的链接看成投票，指示了重要性。

http://www.cnblogs.com/rubinorth/p/5799848.html
http://www.cnblogs.com/en-heng/p/6124526.html
http://blog.jobbole.com/71431/
http://blog.csdn.net/hguisu/article/details/7996185

社区发现(Community Detection)算法

目前的k-truss 算法主要是基于内存的算法、基于 I/O 操作的算法和基于 mapreduce 分布式算法.

从概念上讲，k-truss 基于三角形的定义比 k-core 的定义更加严格，因此被称为网络的基本构建块。例如在一个社交网络中，一个三角形意味着三个朋友拥有非常紧密的关系，或者两个人拥有一个共同的朋友。因此，k-truss 通过强制所有的边中包含至少(k−2)个三角形，进而加强到每条边都拥有至少(k−2)强关系。直观地说，本文在一个社交网络中两个人拥有的共同的朋友越多说明他们之间的关系越紧密。相反，k-core 仅仅是简单的边连接关系(即顶点的度)，只能整个朋友圈中的每个朋友都拥有很多朋友，但是不去强调任意两个朋友之间的关系是否非常紧密。

特别说明的是图 G中没有 4-core结构和 5-truss 结构存在。即图 G 中没有所有顶点的度都大于 4 的子图和每条边都至少被(5−2)=3 个三角形所利用的子图。

聚类系数

聚集系数是表示一个图形中节点聚集程度的系数，证据显示，在现实的网络中，尤其是在特定的网络中，由于相对高密度连接点的关系，节点总是趋向于建立一组严密的组织关系。在现实世界的网络，这种可能性往往比两个节点之间随机设立了一个连接的平均概率更大。这种相互关系可以利用聚类系数进行量化表示。
按照图形理论，聚集系数是表示一个图形中节点聚集程度的系数，证据显示，在现实中的网络中，尤其是在特定的网络中，由于相对高密度连接点的关系，节点总是趋向于建立一组严密的组织关系。在现实世界的网络，这种可能性往往比两个节点之间随机设立了一个连接的平均概率更大。
在很多网络中，如果节点v1连接于节点v2，节点v2连接于节点v3，那么节点v3很可能与v1相连接。这种现象体现了部分节点间存在的密集连接性质。例如，在无向网络中，可以用聚类系数[1] （CC）来表示v2的聚类系数：

其中：k表示节点v2的所有相邻的节点的个数，即节点v2的邻居。
n表示节点v2的所有相邻节点之间相互连接的边的个数。

k-truss

继续移除支持度最小的边，然后重复跌代。直到图中没有边可以删除。此时输出的子图G,即为 4-truss。此时发现图中还有边存在，继续增加k值为 5，重复上面步骤，发现最后移除不符合条件的边后，没有剩余边存在，换句话说不存在 5-truss。这样就找到了此图的极大k-truss 为 4-truss，

不断地去判断顶点个数n是够大于等于当前顶点的度。当扫描到顶点g时，发现顶点度大于等于 5 的顶点有 c、d、e、f、g 一共为5 个，正好符合上述条件顶点的个数大于等于当前顶点 g 的度数 5。之后在邻接表中找到度数为 5的最后一个顶点即 q。此时顶点 c、d、e、f、g、q 构成一个新的子图 G’。在这个新图中保留各个边的支持度值.