复杂网络中的节点相似性

在机器学习领域,很多时候需要衡量两个对象的相似性,特别是在信息检索,模式匹配等方向上。一般情况下,相似性与距离是都是为了描述两个对象之间的某种性质。但在实际使用的时候,需要根据具体的情况来选择合适的相似度或者距离函数。

相似性与距离

首先,我们来看一下相似性函数的含义。对于两个对象 x,y \in X, 相似性函数 s:X\times X\rightarrow \mathbb{R} 是将 X\times X 映射到实数域 \mathbb{R} 的有界函数,i.e. 存在上下界使得 s_{min}\leq s\leq s_{max}, 它具有以下两个性质:

  1. 自反性:s(x,x)=s_{max} 对于所有的 x\in X 都成立;
  2. 对称性:s(x,y)=s(y,x) 对于所有的 x,y\in X 都成立;

一般情况下,不要求相似度函数具有三角不等式的性质。相似度越大,表示两个元素越相似;相似度越小,表示两个元素越不相似。

相似度

其次,我们来看一下距离函数的含义。对于两个对象 x,y\in X, 距离函数 d:X\times X\rightarrow \mathbb{R}^{+}\cup\{0\} 是将 X\times X 映射到非负实数域的函数,它只存在下界 0, 并不存在上界,它具有以下三个性质:

  1. 自反性:d(x,x)=0 对于所有的 x\in X 都成立;
  2. 对称性:d(x,y)=d(y,x) 对于所有的 x,y\in X 都成立;
  3. 三角不等式:d(x,y)+d(y,z)\geq d(x,z) 对于所有的 x,y,z\in X 都成立。

距离越小,表示两个元素越近;距离越大,表示两个元素越远。

距离

相似度(Similarity)

对于欧式空间 \mathbb{R}^{n} 中的两个点 A=(a_{1},a_{2},\cdots,a_{n})B=(b_{1},b_{2},\cdots,b_{n}) 而言,可以多种方法来描述它们之间的相似性。

余弦相似度(Cosine Similarity)

\text{Cosine Similarity}(A,B)=\frac{A\cdot B}{||A||_{2}\cdot ||B||_{2}}=\frac{\sum_{i=1}^{n}a_{i}b_{i}}{\sqrt{\sum_{i=1}^{n}a_{i}^{2}}\cdot\sqrt{\sum_{i=1}^{n}b_{i}^{2}}}.

根据 Cauchy 不等式可以得到 Cosine Similarity 的取值范围是 [-1,1].

Pearson 相似度(Pearson Similarity)

\text{Pearson Similarity}(A,B)=\frac{cov(A,B)}{\sigma_{A}\cdot\sigma_{B}}=\frac{\sum_{i=1}(a_{i}-\overline{A})\cdot(b_{i}-\overline{B})}{\sqrt{\sum_{i=1}^{n}(a_{i}-\overline{A})^{2}}\cdot\sqrt{\sum_{i=1}^{n}(b_{i}-\overline{B})^{2}}}.

其中 \overline{A}=\sum_{i=1}^{n}a_{i}/n, \overline{B}=\sum_{i=1}^{n}b_{i}/n. 同样根据 Cauchy 不等式可以得到 Pearson Similarity 的取值范围是 [-1,1].

Pearson 系数

Dice 相似度(Dice Similarity)

\text{Dice Similarity}(A,B)=\frac{2\sum_{i=1}^{n}a_{i}b_{i}}{\sum_{i=1}^{n}(a_{i}^{2}+b_{i}^{2})},

其中 AB 不能同时是零点,并且由均值不等式可以得到 Dice Similarity 的范围也是 [-1,1].

除了欧式空间的点之外,在有的情况下需要对两个集合 AB 来做相似度的判断。特别地,欧式空间 \mathbb{R}^{n} 里面的点可以看成 n 个点所组成的集合。因此,下面的集合相似度判断方法同样适用于欧式空间的两个点。

Jaccard 相似度(Jaccard Similarity)

对于集合 AB 而言,

\text{Jaccard Similarity}=\frac{|A\cap B|}{|A\cup B|} = \frac{|A\cap B|}{|A|+|B|-|A\cap B|},

其中,|\cdot| 表示集合的势,并且 Jaccard 相似度的取值范围是 [0,1]. 越靠近 1 表示两个集合越相似,越靠近 0 表示两个集合越不相似。

两个集合 A 和 B

重叠相似度(Overlap Similarity)

对于集合 AB 而言,

\text{Overlap Similarity}=\frac{|A\cap B|}{\min\{|A|, |B|\}}

= \max\bigg\{\frac{|A\cap B|}{|A|}, \frac{|A\cap B|}{|B|}\bigg\}

= \max\{P(B|A), P(A|B)\},

其中 P(B|A), P(A|B) 指的是条件概率,意思分别是 A 发生的时候 B 同时发生的概率,B 发生的时候 A 同时发生的概率。重叠相似度的另外一个名称是 Hub Promoted(HP),它主要用于计算两个集合的重叠程度。

Overlap Similarity

类似的,可以将重叠相似度中的 min 函数换成 max 函数,那就是所谓的 Hub Degressed(HD),用公式来描述就是

\text{HD}(A,B)=\frac{|A\cap B|}{\max\{|A|,|B|\}},

它可以用于描述两个集合不重叠的程度。

距离(Distance)

欧氏距离(Euclidean Distance)

d_{2}(A,B)=\sqrt{\sum_{i=1}^{n}(a_{i}-b_{i})^{2}}.

另外,如果将 2 进行推广,则可以引导出 L^{p}(1\leq p\leq  +\infty) 距离如下:

d_{p}(A,B)=\bigg(\sum_{i=1}^{n}|a_{i}-b_{i}|^{p}\bigg)^{\frac{1}{p}}, 其中 p\geq 1.

d_{\infty}(A,B)=\max_{1\leq i\leq n}|a_{i}-b_{i}|.

欧氏距离

复杂网络中的节点相似性

在复杂网络 G=(V,E) 中,G 表示顶点集合,E 表示边的集合。为了简单起见,这里暂时是考虑无向图的场景。对于顶点 x \in V 而言,N(x) 表示其邻居的集合。在复杂网络中,同样需要描述两个顶点 x,y\in V 的相似性,于是可以考虑以下指标。

无标度网络

共同邻居相似度(Common Neighbours Similarity)

对于两个顶点 x,y\in V 而言,如果它们的共同邻居数越多,表示它们的相似度越高,反之,相似度越低。

CN(x,y)=|N(x)\cap N(y)|=\sum_{u\in N(x)\cap N(y)}1.

共同邻居

所有邻居相似度(Total Neighbours Similarity)

类似地,将顶点 xy 的邻居求并集,也可以得到一个指标,TN(x,y)=|N(x)\cup N(y)|.

Preferential Attachment

PA(x,y)=|N(x)|\cdot |N(y)|, 它将 xy 的邻居数乘起来,获得一个指标。

Jaccard 相似度(Jaccard Similarity)

如果将两个节点 xy 的邻居分别作为两个集合 N(x), N(y), J(x,y)=CN(x,y)/TN(x,y) 就可以作为顶点 xy 的 Jaccard 相似度指标,其相似度是通过邻居来衡量的。

Sorensen-Dice 相似度(Sorensen-Dice Similarity)

SI(x,y)=\frac{2|N(x)\cap N(y)|}{|N(x)|+|N(y)|},

该相似度与 Jaccard 相似度有恒等变换,J(x,y)=\frac{SI(x,y)}{2-SI(x,y)}SI(x,y)=\frac{2\cdot J(x,y)}{1+J(x,y)}.

Hub Promoted 相似度

该相似度描述了顶点 xy 的重叠程度,

HP(x,y) = \frac{|N(x)\cap N(y)|}{\min\{|N(x)|,|N(y)|\}}.

Hub Depressed 相似度

HD(x,y)=\frac{|N(x)\cap N(y)|}{\max\{|N(x)|,|N(y)|\}}.

复杂网络的社区

好友度量(Friend Measure)

\text{Friend-measure}(x,y)=\sum_{u\in N(x)}\sum_{v\in N(y)}\delta(u,v),

其中 \delta 用于判断 u,v 之间是否有边相连接。如果相连接,则取值为 1, 否则取值为 0.

Adamic Adar 相似度(Adamic Adar Similarity)

A(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{\ln |N(u)|},

因此,0\leq A(x,y)\leq \frac{CN(x,y)}{\ln(2)}. 事实上,当 u\in N(x)\cap N(y) 时,|N(u)|\geq 2. A(x,y) 越大,表示顶点 xy 的相似度就越高;反之,如果 A(x,y) 越小,表示顶点xy 的相似度就越低。Adamic Adar Algorithm 相当于在共同邻居的计算上增加了权重,如果 x,y 的共同邻居 u 拥有较多的邻居,则降低权重,否则增加权重。

Resource Allocation 相似度(Resource Allocation Similarity)

RA(x,y)=\sum_{u\in N(x)\cap N(y)}\frac{1}{|N(u)|},

该相似度函数与 Adamic Adar 相似度类似,只是分母上没有增加对数函数而已。

参考文献:

  1. Silva, Thiago Christiano, and Liang Zhao. Machine learning in complex networks. Vol. 2016. Switzerland: Springer, 2016.
  2. Barabási, Albert-László. Network science. Cambridge university press, 2016.
  3. Wang, Peng, et al. “Link prediction in social networks: the state-of-the-art.” Science China Information Sciences 58.1 (2015): 1-38.

在新加坡的这五年—生活篇(七)

留学在外,衣食住行是所有学生都必须要关注的事情。还未出国之前,笔者总觉得在外留学需要每天自己准备食物,然后刚到新加坡的第一天,就彻底地打消了这个念头。新加坡是一个多元化的国家,它们的饮食亦是如此,除了当年下南洋的华人所创造的诸多美食之外,还有周边国家的人民所传入的食物。除此之外,新加坡人日常工作繁忙,也少有人能够在家长期做饭。虽不能够经常在家做饭,但在新加坡的各个社区和住宅楼附近,都布满了食阁,里面充满了各国的食物,足以满足周边居民的饮食需要。

NUS 的食阁(摘选 NUS 官网)

对于学生而言,如果日常都要去周边食阁吃饭,则还是不太方便,但是在 NUS 的内部的各个学院其实都有相应的食堂。第一次到 NUS 的时候,是从 West Coast Plaza 出发,穿越 Clementi Woods,就走到了 NUS 的工学院(Faculty of Engineering)。在工学院的食堂,其实就有各个国家的食物,不仅有中式的快餐,还有印尼烧烤等诸多食物。在食堂附近,还有着一年到头都开着的麦当劳(Mcdonalds),无论是在日常生活还是除夕期间,都可以去麦当劳购买快餐。每个学院都有自己的食堂其实会相对方便,毕竟每个院系的学生和老师都在相应的院系走动,近距离的食堂确实也能够给大家带来更多的方便。当时在 NUS 当助教的时候,是带 MA1505 和 MA 1506 两门课,而这两门课的开设地点通常都是在工学院(除了在 2014 – 2015 学年改到了 UTown 的 ERC),在工学院讲课自然是在工学院吃饭最为方便。而工学院的食堂则是位于 Central Library 的对面,只要坐校车就可以轻松地到达食堂。

FacultyofEngineeringCanteen_1
Faculty of Engineering 的食堂

NUS 的工学院食堂里面的店面相对丰富,不仅包括中式杂菜饭,还有印尼烧烤等诸多选择,足以满足不少教职工的需要。毕竟新加坡是一个多元化的国家,由不同的民族组成。所谓杂菜饭,就是跟国内的食堂打饭一样的性质,商家会将不同种类的菜分门别类的放好,顾客想吃什么菜只需要告诉商家就行,最后商家会根据顾客的需要将其打包或者装盘。不过 NUS 的 Faculty of Engineering 的打包看上去就是很简单,Science 的鸡肉饭至少会用一个饭盒。

2013年1月30日的朋友圈
人生第一个朋友圈(20130130)

对于理学院的学生而言,其实去 Science 的食堂是最方便的,当年只要从理学院的大门进去,就能够很容易地找到 Science 食堂。在 2010 – 2015 年期间,Science 食堂一直维持原样,直到 2017 年底 Science 食堂才得以重新翻修。后续如果有机会重返新加坡,一定会去新的 Science Canteen 再吃一顿。

FacultyofScience_1
理学院的标志
FacultyofScienceCanteen_1
以前的 Science Canteen

除了在各个学院的食堂之外,NUS 宿舍区的食堂其实也独具特色。对于博士生而言,日常的饮食自然是可以在学院的食堂解决,但是每个学院的食堂周末都是不开门的。事实上,每次到了星期六下午 13:00 之后,各个学院的食堂都会关闭,直到下周一才会重新开始营业。于是每到周末的时候,博士生们除了选择外出吃饭之外,还可以选择在 UTown 或者 Prince George Park 的食堂吃饭。UTown 和 Prince George Park 是研究生和博士生能够选择的宿舍区,其中有很多类型的宿舍可供选择,无论是有空调的屋子,没有空调的屋子,还是家庭式的独立房间都是可以让博士生根据自身的需要进行选择的。

NUS UTown Residence

周末除了能够在宿舍区的食堂吃饭之外,学生们还可以选择去周边的食阁寻找美食。距离 NUS 比较近的住宅区是 Clementi(金文泰),而在金文泰比较有名的小吃则是“黄土地西安小吃”,这家店铺主要是卖羊肉泡馍,肉夹馍,凉皮等食物。而这些美食恰好就是 NUS 的食堂所没有的,因此数学系里面的几位西安籍的博士生都非常喜欢去这家店。从 NUS 的数学系 S17 去 Clementi 其实只需要从 AYE 上乘坐 97,197,198,963 等线路的公交车就可以顺利抵达,不过下车之后自然是需要步行一段时间的。

S17 到 Clementi 的线路

新加坡的各个住宅区都设有食阁,食阁里面的食物自然是可以提供外带服务的。有几次笔者就将凉皮和肉夹馍自行携带回 S17 的办公室享用。

星期日的晚餐(20131006

除了来自中国的面食之外,在新加坡也有不少日本拉面店。在新加坡吃日本拉面的地点也有许多,而笔者常去的地点包括 Vivo City, Buona Vista 和 Holland Village 。笔者吃日本拉面其实是受到了卫同学的影响。自从 Circle Line 开通了之后,从 NUS 的 S17 去 Vivo City 也很方便,只需要在 Kent Ridge MRT Station 乘坐 Circle Line 就可以轻松抵达 Vivo City,在这里有日本拉面店中比较出名的是面屋武藏(Menya Musashi)。同时,新加坡的荷兰村(Holland Village)也是店铺林立,它属于新加坡别有风味的休闲购物区。在荷兰村有不少的酒吧,商店,饭馆等,只要有钱有时间有胃口,在这里就可以享用到各国的美食。在 Holland Village 的拉面店也有许多,包括 Yushimura 日本拉面,三宝亭(Sanpoutei Ramen),翡翠拉面小笼包等,只不过翡翠拉面小笼包中的拉面一般是中式拉面。

面屋武藏(20131113

日常的饮食除了食堂和各个餐馆之外,各种类型的自助餐也是新加坡的特色之一。刚去新加坡的时候第一次吃的自助餐就是四川火锅自助,在 Block 602 附近就有添一点火锅和川江号子。在节假日最常做的一件事情就是在中午的时候吃自助火锅,到了晚上之后就完全不需要吃晚饭了。新加坡的自助餐除了中国的四川火锅之外,还有各种各样的海鲜自助餐。其中去的次数较多的就是维也纳海鲜,虽然说是海鲜自助餐,但是也会提供牛排,鸡翅等食物。整体的质量较高,推荐享用。

维也纳海鲜(20131019

每次到了新加坡春节的时候,包括 NUS 校园内部食堂在内的许多餐厅都会暂停营业。在这种时候,博士生们除了吃麦当劳或者自己做饭之外别无选择。不过在 NUS 的 Faculty of Engineering 就有一个麦当劳,在 Kent Ridge MRT Station 也有一个汉堡王(Burger King),每逢节假日笔者都有可能出现在这里吃汉堡。

正月初二的麦当劳(20140201)

到了 2014 年,基本上是 2010 级的博士生准备毕业的时候,毕竟这是博士生面临着发表论文和撰写毕业论文的关键阶段了。在 2014 年 7 月 12 日,2010 级第一位提交博士论文的博士生何同学离开了新加坡,准备再去美国攻读一个博士学位。在送别了何教授之后,笔者和一些朋友一起去 Geylang 的串烧工坊吃了顿烧烤。不过新加坡的啤酒是真的十分昂贵,一瓶青岛啤酒在餐馆里面可以卖到 8 新币(折合人民币 40 元左右)。

串烧工坊(20140712)

其实在 2014 年上半年,笔者的论文课题已经基本完成,关键的核心步骤已经写好。而到了 2014 年的下半年,笔者的毕业论文基本上已经写好,只需要整理完成即可。那半年的主要工作就是撰写毕业论文和当助教,到了 2015 年的时候,笔者已经顺利地提交了博士论文并且回国过春节。在 2015 年 4 月份答辩结束之后,在回国找工作之前,笔者专门去了一次位于宏茂桥的龙海鲜螃蟹王,这里的螃蟹米粉真的是一绝,螃蟹汤拌米粉真的是非常好吃。2012 年和司北吃螃蟹是在新加坡河边上的珍宝海鲜楼,后来 2017 年在日本东京的时候也与司北在日本居酒屋共进晚餐,只是不知道下次跟司北一起吃饭是在何时何地了。(未完待续)

龙海鲜螃蟹王(20150519)