算是上篇的一个补遗

Networkx

这是一个python库，封装了几乎所有网络分析所需要用到的类和函数。可以构造directed和undirected网络，把网络写成各类格式的文件，有各种属性（Degree，Betweenness，Pagerank等等）的算法。上手简单，用easy_install和macport都能安装。

igraph

一个多语言的库，我主要用到的它的R Package，能够帮助我比较方便的进行一些统计方面的计算和绘图。

Gephi

一个跨平台的网络分析工具，我主要用它来进行视觉化。用networkx把网络serielize成GraphML格式的文件，然后用gephi进行视觉化。它还有很多plugins可以安装。

Guess

我的教授自己写的网络分析工具，可以自己写很多script导入，灵活性比较高。

另外就是Twitter和微博的API，大概就这些，以后有新的再加。

这学期的一个课程项目，写出来跟大家分享一下。

一直都会有这种说法，Twitter上的中文用户比微博上的用户更开放，更喜交流。正好这个学期在上网络分析的课，就试图用课上的知识分析一下两边的网络所呈现的状态。

• 数据收集

我们先用follower数定义出top用户，按照follower数由大到小排rank，取前100做为top用户。微博本身提供了排行榜，其中人气榜是按照follower数量来的。我们先抓取了人气总榜的前100，后来意识到这个总榜里大多数都是明星，跟Twitter的top中文用户差别太大，于是又抓了微博上草根榜前100。

Twitter中文数据比较难办，我参考Twitese的代码，自己写了一个很简易的版本。抓了14w条最近发的推、简介和用户名里有中文的用户，另外写了一些额外的条件保证韩国和日本友人不要跑到我的数据库里来。最后按照Follower数取了前100.

然后分别分析这三个top用户组之间互相关注的情况，得到了三个用户网络分别是Top_Twitter（Twitter top中文用户），Top_Weibo（微博人气总榜top）和Top_G_Weibo（微博草根人气榜top）。其中每一条Edge都代表一个关注关系，每一个点都代表一个用户。这个网络是directed的，就是说从节点A到节点B的edge和从节点B到A的edge是两条edge。

• 分析

用户交流：

从下面这个图，大概就能看出三个网络中用户的联系程度了。图中点的颜色越红，代表它受到其他点的关注读越高，Top_G_Weibo里有很多孤立的点。：

详细数据如下。

从这个表里可以看到，Top_Twitter这个网络的关注关系的总量差不多是Top_Weibo的两倍，是Top_G_Weibo的5倍左右。这说明在这个三个网络中间，Twitter用户更愿意关注别人。

Global clustering系数代表了点与点之间联系的紧密程度。系数越大，联系越紧密。从表里面同样可以看到，Top_Twitter网络里的节点联系更紧密。

Strong connected component指的是，如果网络中的一个子网络里没一个节点都能到达另外一个节点，那么这个子网络就是整个网络的一个strong connected component。详细看下表：

表里第一行是component的个数，第二行是每个component里的节点数的列表。Top_Twitter里只有一个点可能不被其他点reach到。而Top_G_Weibo里这样的点多达30个。

另外一个重要的数据是每日发推量。Top_Twitter里的用户平均每日发推数量是10.62，Top_Weibo里是4.56，Top_G_Weibo里是4.35。从这个数据也可以看出Twitter中的top中文用户更活跃，愿意发表意见与人交流。

用户多样性：

用户多样性是一个不太好考查的东西，我们讨论后决定，用用户所在地的分布来分析用户多样性。

三个图中的圆圈上的每一个点都是一个地点，从每个点伸出去的轴都是在同一地点的用户。可以看到三个网络中北京的用户都是处于绝对多数的地位。圆圈的大小则代表100个用户所在地的多样性。Top_Weibo的中心圆最小，明星大多都在香港北京台湾…因为Top_Twitter和Top_G_Weibo里有太多用户的地点是Unknown或者Other，所以他们的多样性，还需要进一步检查。另外注意到Twitter网络里有些用户来几个热点事件地点。

另外我们还考查了几个拥有最大用户数的地点之间的关系：

北京真是一个超大的hub。另外除了中间那个爆多明星的网络，另外两个网络都显示广东跟北京互动的最多。

• 讨论

整个项目还有很多可以改进的地方，像location就可以尝试抓取更准确的数据。另外抓取的三个网络全部都是搞biased的网络，如果需要知道整个网络的状况，需要更随机的取样。另外如果可以分析retweet、mention和各个推的内容，就能更准确的分析节点之间的互动了。

下个学期注册了独立学习课程，准备把这个项目继续下去。

最近开始做Project Euler里的题目，做到第三题就有点小小的卡住了。第三题的题目如文章标题，需要找到一个自然数的最大质因数。

假设输入的自然数是N，最直接的方法是从小到大算出N的每一个因数，然后再判断这个因数是不是质数。显然这种算法的复杂度很高。在最坏情况下是O(N^2)的复杂度。

自己想更好的算法，没有想出来，只好借助于Google，看到了这样一个思路：

函数biggest(N)是求最大质因数的函数。

在函数里，先将N里的2除完，余下的商M是0或者一个奇数。如果是0，那么N是2的次方，2就是N的最大质因数。

如果余下的商是奇数，那么将M用从3开始的到sqrt(M)+1的奇数J试商。如果能被奇数J除尽，那么J一定是质数。再递归求M/J的商的最大质因数I，并将I与J比较，取较大的一个。

这个算法的巧妙之处就是用3开始的奇数试商。比如如果M能被3除尽，那么将3和biggest(M/3)比较。这样的递归，可以保证把M中的3都除尽，这样以来，3的次方就不会出现在返回结果里。同理，5、7、11这些质数也会被除尽。因此只要在试奇数商的时候被除尽了，那么这个奇数就是质数。

算法实现如下：

import sys
from math import sqrt

def find_largest_primef(n):
    is_prime = True
    if n == 2:
        return n
    if n%2 == 0:
        print n, 'getting rid of 2s..'
        is_prime = False
        return find_largest_primef(n/2)
    else:
        for i in range(3,int(sqrt(n))+1,2):
            print 'try ..', i
            if n%i == 0:
                print 'n: ', n, 'i: ', i
                is_prime = False
                return pick_larger(i, find_largest_primef(n/i))
    if is_prime:
        print n, 'is prime!'
        return n

def pick_larger(first, second):
    if first >= second:
        return first
    else: return second

if __name__ == '__main__':
    print find_largest_primef(int(sys.argv[1]))

上了两个月的学了，可以稍微写点东西了。

1. 背景信息

标题已经说明，现在我在密歇根大学信息学院读两年制的MS in Information。需要注意的这里不是Information System，也不是Information Science，只有一个单词。我写简历的时候自作主张的写成MS in Information Science，被就业指导中心的人专门提出来需要修改。

学院很年轻，90年代成立的吧，前身是图书馆学系，去年刚刚搬到学校新建的North Quad楼。更多背景信息可以去这里看。MSI下设好多个方向，有Human  Computer Interaction这种比较热门的，也有传统方相如Library and Information Science等。我现在是HCI方向的，准备加Information Analysis and Retrieval做第二个方向。

这个信息学院在US News上排名前三，院长讲话的时候说“welcome to one of the finest iSchool in the States”。

2. 招生情况

新生报到的时候，介绍会上院长说今年一共招了170个左右的研究生，其中150个左右的硕士。这只是大概的数字。去年申请的时候好像在网站上看过说就读学生一共不到400个，后来网站改版我再也找不到这个数字了……

今年中国学生一共有20个左右吧，其中博士生大概两三个。整个学院很跨学科，所以学生背景很丰富。就我了解的，中国学生的背景有来自各类学校的各种专业：北大、清华、北邮、对外经贸等等，MIS、人机工程、CS等等。

学校招生办公室总在招学生临时工，我觉得太没意思所以从来没申请过，哪位同学有兴趣去干这类工作的话应该会有更多信息。

3. 学校周边环境和生活

Ann Arbor，距底特律大概1个小时车程。典型大学城，downtown就在中校旁边。Ann Arbor的U-M分为中、北、南三大校区，校园面积号称全美数一数二。不同校区有学校免费公车链接，另外市政的公交用学生卡可以免费坐。校巴一直到凌晨3点还有，所以住在学校提供的宿舍没有车去图书馆刷夜也是比较方便。市政公交比较坑爹，一般10点后就没有了，周末六点后就没有了。

小镇消费，应该比大城市便宜。我住的学校研究生公寓，两人一个Town House，上层卧室下面客厅厨房，地下室有洗衣机和烘干机，东西坏了打电话给Housing第二天就有人来修，一个月571包水电网。我选择这个房子最大的理由就是省事。同学大多住在校外，房租一般不到500，便宜的400出头。有的包一些bill，有的完全不包。我食量较大，所以会在吃上面花很多钱。这里午、晚餐如果不自带的话6块左右可以搞定。自己做更便宜。

但是我听到几个美国学生抱怨过这里物价较高，不知是否可信。

已经在这里住了一年的室友告诉我这里很安全。我也觉得还蛮安全的。学校保卫处时不时会发Crime Alert，两个月收到三四封的，一些打劫和骚扰的案子。这种透明度让我感觉到更安全。

夜生活很丰富，刚刚开学跟同学去夜店和脱衣舞俱乐部疯过一次。

4. 学习生活

累得跟狗似的。

周一到周五白天上课晚上图书馆，周六周天白天图书馆晚上图书馆。其中穿插着各种课程项目的小组会议。通宵过几次，平均每天1点半睡觉。图书馆晚上1点都还人满。我喜欢这个气氛。

当然你也可以换一种方式学习，不要像我一样选那么多课……

选课很自由。

5. 就业、实验室和social

刚来两个月，就业情况不好说，听学院宣传还是可以的。每周都能收到很多招聘信息，前几届前辈们实习就业的公司看起来也很光鲜。只是我没有什么数据。

我估计会继续申PhD，所以现在正在找一个PhD师兄帮他写代码，争取明年能找一个教授帮他做点事情，然后明年秋天能搞一个TA或者RA来付学费。

6. 其他

U-M最出名的应该是橄榄球了，这学期几乎每周都有比赛，所以周末的交通流量似乎比平时大很多。

最后贴几张照片吧：

• 体育场附近的小公园：

• 中校的大钟楼

• 研究生院的自习室

• 北校图书馆窗外

比如一个数组[4,6,7]可以输出成：

0 0 1
0 1 1
0 1 1
1 1 1
1 1 1
1 1 1
1 1 1

连续的1可以被看作一个直方。

基本思路：将输出看作一个矩阵，矩阵的大小是由原数组的长度N和数组中最大的数字M决定。左上角的坐标是（0，0），右下角的是（N，M）。则原问题被转化为，如何将原来的一维数组转化为这样一个二维数组，二位数组的每一个元素对应相应的坐标打印出来的数字是0还是1。以直方图的第一列为例，新的二维数组是a[M][N], 那么a[*][0]这一列则应该是0，0，0，1，1，1，1。具体代码如下：

#include <stdio.h>

void main(){
    int array_origin[4] = {4,6,10,9};
    int array_print[10][4] = {{0}};
    int i, j;
    for (i=0; i<4; i++){
        for (j=0;j<array_origin[i];j++){
            array_print[9-j][i] = 1;
        }
    }
    for (i=0; i<10; i++){
        for (j=0; j<4; j++){
            printf("%d ", array_print[i][j]);
        }
        printf("\n");
    }
}

另外一个有趣的小现象后面的故事：
大家可以尝试一下，142,857这个数与2、3、4、5、6相乘的6个不同结果，全是由“1”，“2”，“4”，“5”，“7”，“8”这六个数排列组合而成的。

这是为什么呢？

原因在于1/7的结果的是0.142857142857…..无限循环，之所以能这样循环，是因为1除以7的展开式里，商为1的时候余3，商为4的时候余2，……，一直到商为7的时候余1，余1的时候开始循环。因为一个数除以7只能有6个余数，所以这个无限寻婚小数的周期是6。

那142,857和7的余数相乘的结果的奥秘也就不难看出了，1除以7的余数是3、2、6、4、5、1，导致的商是1、4、2、8、5、7，那么如果是2除以7，则是把上面的余数的循环变成了从4开始，商的循环变成了从2开始，但是商的循环中的那几个数还是不变的。2/7 = 2 * (1/7)，也就等于2*0.142857  循环，组成循环的数字不会变。同理，142857与3，4，5，6的乘积仍然是那几个数字的排练组合。