Social and Economic Networks: Models and Analysis这门课是斯坦福大学在Coursera上的一门公开课，恰好这段时间开始开放，加上评分还不错，于是打算来听听，由于自己对Social Network Analysis不是特别熟悉，所以就从第一节课一些基本概念开始，在这个博客留下一些笔记吧。

第一节课主要涉及社会网络分析的一些基本问题和概念，例如为什么Facebook这样的社会网络里大部分人之间都具有很短的图上距离？社会网络如何影响人类行为？下面是具体内容：

1.n个结点可以形成多少种不同的网络？

考虑所有可能存在的边的数量为 \(n+(n-1)+\cdots+1=\frac{n(n+1)}{2}\) ，所以可能形成的网络的数量为 \(2^{\frac{n(n+1)}{2} }\) 。

2.Network表示方法

用邻接矩阵G表示，若 \(G_{ij}=1\) ，表示存在一条从顶点i到j的边；若为无向图，则G为对称矩阵，若为有向图，则不一定；若为带权图，则 \(G_{ij}\) 表示边 \(i\rightarrow j\) 的权重，否则，1表示连通，0表示不连通。

3.图相关概念的基本定义：

• Path（路径）: a walk \((i_1, i_2, \cdots, i_K)\) with each node \(i_k\) distinct
• Cycle（环路）: a walk where \(i_1=i_K\)
• Geodesic（测地线）: a shortest path between two nodes
• Components(连通分量): maximal connected subgraph
• Diameter（直径？）:  largest geodesic (largest shortest path)

• Neighborhood（邻居）: $$N_i(g) = { j

  G_{ij}=1}$$

• Degree（度数）: \(d_i = # N_i(g)\)

4.Erdos‐Renyi Random Graphs

这是一个很重要的随机图模型，概念很简单：初始n个点，然后任意两点之间边存在的概率为p，整个图表示为G(n, p)。

关于这个Erdos-Renyi随机网络，有一些特性：

• 如果所有结点的平均度数 \(d(n) \gt (1+\epsilon) log(n) some \epsilon>0\) ，那么整个网络很可能是连通的；
• 如果 \(d(n) \gt (1+\epsilon) log(n) some?\epsilon>0\) 并且 \(\frac{d(n)}{n}\rightarrow 0\) ，那么当n足够大时，网络的平均路径长度和Diameter将正比于 \(\frac{log(n)}{log(d)}\) 。

5.树

树也是一种特殊的网络，这里考虑一种特殊的树，其形成方式为：

(a)初始一个根节点

(b)根结点产生d个子节点

(c)b中生成的d个子节点每个再产生(d-1)个子节点

...... [](/images/post/2014/10/1.jpg)这种树在经过l步之后，将包含 $$1+d+d(d-1)+\cdots +d(d-1)^{l-1}=1+\frac{d((d-1)^l-1)}{(d-2)}\approx (d-1)^l$$ 个节点。 6.Chernoff Bounds 若X是一个二项分布的随机变量，那么 $$P(E[X]/3\le X \le 3E[X])\gt 1-e^{-E[X]}$$ 。 应用到ER图中，那么顶点度数比较靠近平均值d的概率 $$P(d/3\le d_i \le 3d)\gt 1-e^{-d}$$ 。 7.Clustering What fraction of my friends are friends of each other? $$Cl_i(g)=#\{\text{kj in g}| \text{k,j in } N_i(g)\}/#\{\text{k,j in } N_i(g)\}$$ Average Clustering: $$Cl^{Avg}(g)=\sum_iCl_i(g)/n$$