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

网络结构与效应原理李晓明，2012年*秋，人民大学•这是一门什么样的课？•教学目标，教学内容，学生的预期收获•课程的组织，对学生的要求这是一门什么样的课？•从内容上看，是应用数学和计算机科学的基础知识，分析推理网络作用下的一系列经典社会与经济行为的课程•以上述为载体，帮助学生体会文理学科交叉的一种精彩，并训练学生以“计算思维”的观念分析社会学与经济学问题的初步能力•没有先修要求，适合各专业学生这门课的由来（直接）•2009年，从互联网上发现一本即将出版的教材的PDF文件（书稿的早期版本）2010年6月出版，剑桥大学出版社AcourseatCornell2010年12月，康奈尔大学网络课课堂（本科）2010年12月1日AcourseatU.MichAcourseatStanford剑桥大学2011年10月，我们完成了该教材的翻译出版2011年秋2012年春大道理•对于趋势的认识–计算：（科学、技术与工程）（经济、社会与政治）－－“网络分析”是一个天然纽带–计算在人类认识自然进程中作用的演化•计算＋社会科学：跨学科教学的一缕新风–TheChallengesofMultidisciplinaryEducationinComputerScience,byFredRoberts,JCSTJuly,2011•计算思维培养的实例–不仅计算机专业，但是计算机专业的机遇和挑战课程内容概要•出发点–网络，一个已经渗透到人类生活方方面面的概念，理解其作用原理不仅必要且已有可能•主要内容–讨论网络的语言（基础）–网络结构分析–网络行为推理–制度下的聚合行为以若干经济学与社会学经典问题为背景形形色色的网络形形色色的网络•交通运输网，邮政网，电话通信网，计算机网，互联网，万维网•社会关系网，产品供销网，金融借贷网•智能电网，无线网，传感网，物联网•神经网，生物代谢网，食物链（网）•攻守同盟网，恐怖主义网络•…，•人人网，新浪微博网，QQ，…，团购网不同类型网络的依存•互联网（Internet）－物理的、技术的•万维网（WorldWideWeb）－基于互联网的信息网络•人人网－基于万维网的在线社会（社交）网络（OnlineSocialNetwork，OSN）•社会关系网，常常与地域相关（尤其在古代），地域上接近，见面的机会多，建立关系的可能性就大，随着交通工具的发达，社会关系的地域范围扩大技术发展的两重作用（尤其是计算机与通信技术（ICT）的发展）•催化了各种网络的发展–规模变大，范围变广–新型网络的涌现•使分析和理解大规模网络的行为成为可能–行为数据与网络的运行伴生–海量数据分析的能力（计算设施，算法工具）•以社会网络分析为例，以前的分析能力限制在上百个节点，现在可以分析上亿个节点的网络当我们想到“网络”这个词语...“事物”＋“联系”•节点（vertex,point）•边（连接,链接,关系,联系；edge,link,tie）网络的一些基本区分•节点的性质（类型）是否一样？–例如，有些代表人，有些代表机构•边是否有“方向”？–例如，道路的单行线，粉丝明星•节点是否有区别（即便相同性质）？–例如，节点各有特定名称，名称乱了含义不同•边是否有“强弱”（即便没有方向）？–例如，关系的亲疏程度，友好或者敌对•…图论：讨论网络的语言之一•节点，边–完全图，散点图；（群体）–同构，异构•无向图（graph），有向图（directedgraph）•连通，连通分量（分枝），强连通分量•路（path）、桥（bridge）、捷径（localbridge）、距离•二部图（bipartitegraph）•图上的广度优先搜索（breadth-firstsearch）博弈论：讨论网络的语言之二•参与者、策略、回报（收益）•应对、最佳应对；占优策略，非优策略•均衡、纳什均衡–预期的自我实现•纯策略、混合策略•帕累托最优、社会最优•进化博弈，进化稳定，进化稳定混合策略–与经典博弈的关系网络结构分析（社会学和经济学背景下）•边的成因（edgeprediction）–哪些当前没有联系的两个节点将来形成联系的可能性比较大？（三元闭包，同质性）•边的意义–网络中不同位置的边的不同作用（关系强度）•节点的重要性–由结构特征带来的节点的权力，或“权重”•结构的划分，结构的平衡•结构中体现出来的社会性含义一个空手道俱乐部成员之间的社会网络网络结构中的社会性含义示例社会网络中的权力分析示例网络行为推理•群体效应（总体效应）–交通拥堵问题，布雷斯悖论（若结构不合理，增加资源可能反而引起问题）•结构效应–级联，波及，效用•在一定制度下的聚合行为–市场，表决，产权•行为反过来对结构的影响商业网络中的波及效应示例制度示例：关于诚实表决问题•以50%概率拿出其中一个坛子供三人表决用•三人依次，随机取一个看看，放回；不交换意见•每人给出关于坛子是1号还是2号的判断•若多数对了，3人都得奖；否则，3人都受惩罚学习网络关心的核心问题•局部与全局（微观与宏观）–每个人（节点）的局部行为，可能对全局产生什么样的影响？（聚合，aggregation）•节点并不一定刻意追求所导致的全局效果•节点的行为有可能在一定制度的规范下•尺度–在小尺度网络上观察到的原理与现象是否在大尺度上也同样存在•例如，传统社会网络分析中得到的结论，是否在OSN上也成立。推理（reasoning）•Reasoningaboutahighlyconnectedworld•Reason–thecapacityhumanbeingshavetomakesenseofthings,toestablishandverifyfacts,andtochangeorjustifypractices,institutions,andbeliefs.•“推理”不同于“直觉的判断”。推理总是要试图讲出道理•…isawaybywhichthinkingcomesfromoneideatoarelatedidea…教学目标，预期收获•知识内容–宽、广、交叉；–对熟悉知识（事实）的新视角•能力训练–应用计算思维分析推理社会科学问题的初步能力•素质培养–以研究的精神面对问题的态度，AB–“learn”，“study”，“research”•…课程学习后能分析的问题举例•假设人类学家正在研究三个互为邻里的小村庄组成的集合。每个村庄都有30人，包括2-3个大家庭。每个村庄的人们都互相了解自己村庄的人。•人类学家在这三个村庄建立一个社会网络后，发现人们都和自己村庄的人是朋友，和其他两个村庄的人敌对。这就给出了90人形成的网络（因为每个村庄30人），该网络中的边也会带有正关系和负关系的标识。根据所学的概念，这个90人形成的网络是平衡（均衡）的吗？请做一个简明的分析。课程学习后能分析的问题举例•假如一个搜索引擎有两个广告位可以出售。广告位A的点击率为10，B的点击率为5。•有三个广告商有兴趣购买这两个广告位。广告商X对每点击的估价为3，广告商Y对每点击的估价为2，广告商Z的每点击估价为1。分别计算这两个广告位的社会最优分配价格和VCG价格，对你的答案给出简要的解释。课程学习后能分析的问题举例•考虑一个博彩市场，有两匹赛马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赢了呢？课程的组织•教师：李晓明，[e-mail]•助教：孙彩虹，[e-mail]•时间地点–公共教学一楼一层104；周一，18:00-19:30–Officehour:（通常课前1小时，地点待定）•教材：–《网络、群体与市场》（清华出版社，2011）–网上能找到免费英文原版教学内容安排概要•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日考试教学内容安排概要（执行）•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日考试对学生的要求与评估•作业（20％），两篇博客（10％）、课程项目（报告，20％），期末考试（50％）•每次作业必须在下一次课之前交•关于课程博客（@126.com,rucncm1122）–一个公开的、促进学习理解与交流的园地–基本内容是根据课堂学习的方法和思路，寻找实际案例进行分析（具体要求另行安排）•课程项目（报告）根据选课学生的情况另行布置（考试后一周交，1月14日）beijingdaxue