社交网络图的基本理论.pptx

社交网络图的基本理论 清华大学电子工程系网络研究所 黄永峰、汪天一 Tel62792516 Email:yfhuang@ tsinghuawty@ 办公地点：电子系馆5-108 图是网络的数学抽象 图的表示 图的数学表示：邻接矩阵 度（Node Degree） 完全图（Complete Graph） 实际的图大多稀疏 有向图和无向图 有权图和无权图 二分图（Bipartite Graph) 其他种类的图：自边与多重图 网络抽象 WWW directed multigraph with self-interactions Facebook friendships undirected, unweighted Citation networks unweighted directed acyclic Collaboration networks undirected multigraph or weighted Mobile phone calls directed, (weighted?) multigraph 如何描述图的性质？ 度分布（Degree Distribution） 路径（Paths） 路径的数目 距离 寻找最短路径 半径（Diameter） 聚合系数（Clustering Coefficient） 聚合系数（Clustering Coefficient） 其中最重要的性质 Degree distribution: P(k) Path length: h Clustering coefficient: C 例：一维晶格 随机图模型Random Graph Model 参数 随机图模型 随机图模型：边的特征 随机图中的度 度分布 聚合系数