第 1 章 网络 结构与效应原理

第1章网络结构与效应原理第1章网络结构与效应原理这是一门什么样的课？教学目标，教学内容，学生的预期收获课程的组织，对学生的要求第1章网络结构与效应原理这是一门什么样的课？从内容上看，是应用数学和计算机科学的基础知识，分析推理网络作用下的一系列经典社会与经济行为的课程以上述为载体，帮助学生体会文理学科交叉的一种精彩，并训练学生以“计算思维”的观念分析社会学与经济学问题的初步能力没有先修要求，适合各专业学生第1章网络结构与效应原理这门课的由来（直接）2009年，从互联网上发现一本即将出版的教材的PDF文件（书稿的早期版本）2010年6月出版，剑桥大学出版社第1章网络结构与效应原理AcourseatCornell第1章网络结构与效应原理2010年12月，康奈尔大学网络课课堂（本科）2010年12月1日第1章网络结构与效应原理AcourseatU.Mich第1章网络结构与效应原理AcourseatStanford第1章网络结构与效应原理剑桥大学第1章网络结构与效应原理2011年10月，我们完成了该教材的翻译出版第1章网络结构与效应原理2011年秋2012年春第1章网络结构与效应原理大道理对于趋势的认识计算：（科学、技术与工程）（经济、社会与政治）－－“网络分析”是一个天然纽带计算在人类认识自然进程中作用的演化计算＋社会科学：跨学科教学的一缕新风TheChallengesofMultidisciplinaryEducationinComputerScience,byFredRoberts,JCSTJuly,2011计算思维培养的实例不仅计算机专业，但是计算机专业的机遇和挑战第1章网络结构与效应原理课程内容概要出发点网络，一个已经渗透到人类生活方方面面的概念，理解其作用原理不仅必要且已有可能主要内容讨论网络的语言（基础）网络结构分析网络行为推理制度下的聚合行为以若干经济学与社会学经典问题为背景第1章网络结构与效应原理形形色色的网络第1章网络结构与效应原理形形色色的网络交通运输网，邮政网，电话通信网，计算机网，互联网，万维网社会关系网，产品供销网，金融借贷网智能电网，无线网，传感网，物联网神经网，生物代谢网，食物链（网）攻守同盟网，恐怖主义网络…，人人网，新浪微博网，QQ，…，团购网第1章网络结构与效应原理不同类型网络的依存互联网（Internet）－物理的、技术的万维网（WorldWideWeb）－基于互联网的信息网络人人网－基于万维网的在线社会（社交）网络（OnlineSocialNetwork，OSN）社会关系网，常常与地域相关（尤其在古代），地域上接近，见面的机会多，建立关系的可能性就大，随着交通工具的发达，社会关系的地域范围扩大第1章网络结构与效应原理技术发展的两重作用

（尤其是计算机与通信技术（ICT）的发展）

催化了各种网络的发展规模变大，范围变广新型网络的涌现使分析和理解大规模网络的行为成为可能行为数据与网络的运行伴生海量数据分析的能力（计算设施，算法工具）以社会网络分析为例，以前的分析能力限制在上百个节点，现在可以分析上亿个节点的网络第1章网络结构与效应原理当我们想到“网络”这个词语...

“事物”＋“联系”节点（vertex,point）边（连接,链接,关系,联系；edge,link,tie）第1章网络结构与效应原理网络的一些基本区分节点的性质（类型）是否一样？例如，有些代表人，有些代表机构边是否有“方向”？例如，道路的单行线，粉丝明星节点是否有区别（即便相同性质）？例如，节点各有特定名称，名称乱了含义不同边是否有“强弱”（即便没有方向）？例如，关系的亲疏程度，友好或者敌对…第1章网络结构与效应原理图论：讨论网络的语言之一节点，边完全图，散点图；（群体）同构，异构无向图（graph），有向图（directedgraph）连通，连通分量（分枝），强连通分量路（path）、桥（bridge）、捷径（localbridge）、距离二部图（bipartitegraph）图上的广度优先搜索（breadth-firstsearch）第1章网络结构与效应原理博弈论：讨论网络的语言之二参与者、策略、回报（收益）应对、最佳应对；占优策略，非优策略均衡、纳什均衡预期的自我实现纯策略、混合策略帕累托最优、社会最优进化博弈，进化稳定，进化稳定混合策略与经典博弈的关系第1章网络结构与效应原理网络结构分析

（社会学和经济学背景下）边的成因（edgeprediction）哪些当前没有联系的两个节点将来形成联系的可能性比较大？（三元闭包，同质性）边的意义网络中不同位置的边的不同作用（关系强度）节点的重要性由结构特征带来的节点的权力，或“权重”结构的划分，结构的平衡结构中体现出来的社会性含义第1章网络结构与效应原理一个空手道俱乐部成员之间的社会网络第1章网络结构与效应原理网络结构中的社会性含义示例第1章网络结构与效应原理社会网络中的权力分析示例第1章网络结构与效应原理网络行为推理群体效应（总体效应）交通拥堵问题，布雷斯悖论（若结构不合理，增加资源可能反而引起问题）结构效应级联，波及，效用在一定制度下的聚合行为市场，表决，产权行为反过来对结构的影响第1章网络结构与效应原理商业网络中的波及效应示例第1章网络结构与效应原理制度示例：关于诚实表决问题以50%概率拿出其中一个坛子供三人表决用三人依次，随机取一个看看，放回；不交换意见每人给出关于坛子是1号还是2号的判断若多数对了，3人都得奖；否则，3人都受惩罚第1章网络结构与效应原理学习网络关心的核心问题局部与全局（微观与宏观）每个人（节点）的局部行为，可能对全局产生什么样的影响？（聚合，aggregation）节点并不一定刻意追求所导致的全局效果节点的行为有可能在一定制度的规范下尺度在小尺度网络上观察到的原理与现象是否在大尺度上也同样存在例如，传统社会网络分析中得到的结论，是否在OSN上也成立。第1章网络结构与效应原理推理（reasoning）ReasoningaboutahighlyconnectedworldReason–thecapacityhumanbeingshavetomakesenseofthings,toestablishandverifyfacts,andtochangeorjustifypractices,institutions,andbeliefs.“推理”不同于“直觉的判断”。推理总是要试图讲出道理…isawaybywhichthinkingcomesfromoneideatoarelatedidea…第1章网络结构与效应原理教学目标，预期收获知识内容宽、广、交叉；对熟悉知识（事实）的新视角能力训练应用计算思维分析推理社会科学问题的初步能力素质培养以研究的精神面对问题的态度，AB“learn”，“study”，“research”…第1章网络结构与效应原理课程学习后能分析的问题举例假设人类学家正在研究三个互为邻里的小村庄组成的集合。每个村庄都有30人，包括2-3个大家庭。每个村庄的人们都互相了解自己村庄的人。人类学家在这三个村庄建立一个社会网络后，发现人们都和自己村庄的人是朋友，和其他两个村庄的人敌对。这就给出了90人形成的网络（因为每个村庄30人），该网络中的边也会带有正关系和负关系的标识。根据所学的概念，这个90人形成的网络是平衡（均衡）的吗？请做一个简明的分析。第1章网络结构与效应原理课程学习后能分析的问题举例假如一个搜索引擎有两个广告位可以出售。广告位A的点击率为10，B的点击率为5。有三个广告商有兴趣购买这两个广告位。广告商X对每点击的估价为3，广告商Y对每点击的估价为2，广告商Z的每点击估价为1。分别计算这两个广告位的社会最优分配价格和VCG价格，对你的答案给出简要的解释。第1章网络结构与效应原理课程学习后能分析的问题举例考虑一个博彩市场，有两匹赛马A和B；有两个赌客，1和2。设每个赌客的财富量都是w。赌客1相信A赢的概率是1/2，因此B也是1/2。赌客2相信A赢的概率是1/4，因此B是3/4。两个赌客的财富效用都是对数函数，都根据自己的信念下注，要使财富效用的期望最大化。（a）赌客1，2分别应该在赛马A，B上投多少钱？（b）求A和B的均衡赔付率倒数。（c）如果A赢了，赌客1会有多少钱？若B赢了呢？第1章网络结构与效应原理课程的组织教师：李晓明，助教：孙彩虹，时间地点公共教学一楼一层104；周一，18:00-19:30Officehour:（通常课前1小时，地点待定）教材：《网络、群体与市场》（清华出版社，2011）网上能找到免费英文原版第1章网络结构与效应原理教学内容安排概要9月10日 第1章，课程概述；第2章，图论基本概念9月17日 第3章，强联系和弱联系；第4章，网络及其存在的环境9月24日 第5章，正关系与负关系10月8日 第6章，博弈论基础，第7章，进化博弈10月15日 第8章，网络流量的博弈论模型，第9章，拍卖10月22日 第10章，匹配市场；第11章，有中介的市场网络模型10月29日 第12章，网络中的议价与权力11月5日 第13章，万维网结构；第14章，链接分析和网络搜索11月12日 第15章，搜索引擎带来的广告市场11月19日 第16章，信息级联；第17章，网络效应11月26日 第18章，幂律与富者更富现象12月3日 第19章，网络中的级联现象；第20章，小世界现象12月10日 第21章，流行病学12月17日 第22章，市场与信息12月24日 第23章，表决12月31日

第24章，产权；课程内容要点回顾1月7日

考试第1章网络结构与效应原理教学内容安排概要（执行）9月10日 第1章，课程概述；第2章，图论基本概念9月17日 第3章，强联系和弱联系；第4章，网络及其存在的环境9月24日 第5章，正关系与负关系10月8日 第6章，博弈论基础，第7章，进化博弈10月15日 第8章，网络流量的博弈论模型，第9章，拍卖10月22日 第10章，匹配市场；第11章，有中介的市场网络模型10月29日 第12章，网络中的议价与权力11月5日 第13章，万维网结构；第14章，链接分析和网络搜索11月12日 第15章，搜索引擎带来的广告市场11月19日 第17章，网络效应11月26日 第18章，幂律与富者更富现象12月3日 第16章，信息级连；第20章，小世界现象12月10日 第21章，流行病学12月17日 第22章，市场与信息12月24日 第23章，表决12月31日

第24章，产权；课程内容要点回顾1月7日

考试第1章网络结构与效应原