《才斋讲堂》PPT课件.ppt

1、社会科学中的 计算思维浅赏,北京大学李晓明，,传统课程、慕课（MOOC）与翻转课堂,2010年，发现一本书,2011年，将它译成中文,2011年秋，开本科生课,2013年春，开研究生课,2016年春，研究生课（欢迎选修）社会与市场中的计算问题选讲,教师：李晓明，杨智,关心的话题（例）,社会网络演化的原因？ 为什么音乐学院同班同学，20年后有的变得很有名气，有的则一般般，除了才华、运气，还有没有什么别的原因？ 有些新产品进入市场，为什么会采用免费试用、打折促销等手段？ 人们从众，是因为众人正确，还是因为人们天性盲目，或者什么其他原因？ 人类社会为什么会形成“小世界”现象？,今天讨论三个例子,网络

2、中的博弈,小世界与大数据,网络效应下的市场,总体学习目标： 意识到关系（结构）与互动可以作为刻画社会科学问题的两种有效工具； 体会一种基于它们讨论社会科学问题的思维方法,网络中的博弈,学习目标： 通过理解在交通网络中流量均衡的概念及其所导致的状况，体会到在现实中为改善境况不仅需要资源充分，还需要结构合理的道理,网络结构上的博弈,公路交通网 十一长假，是否出门？走哪条路线？ 有意无意中，你会想：别人会怎么样？,体会博弈：一个实验,出6个同学，每人发两张扑克牌，一张红，一张黑 规则 每人独立决定出哪一张牌，不让其他人看见 如果你出的是红牌，无论别人出什么，都得到1元钱奖励回报； 如果你出的是黑牌

3、若其他所有人都出黑牌，你就得4元钱回报； 若有任何一人出红牌，则你就必须支付赔偿1元钱,从这个例子体会博弈论精神,参与人若干，独立 策略每人可能的选择 回报不仅取决于自己，还取决于别人,关心： 作为个人，我怎么能得到较大回报？ 作为社会，总体来看，结果会如何？,网络中的博弈：一个简化的例子,参与人：4000位司机 策略选择：“走上面”和“走下面” 回报：行驶时间（越小越好），显然也取决于他人的策略,有4000辆车，都要从A到B,“均衡” 没人可以得到更好回报的选择状态,C,A,B,D,x/100,x/100,45,45,4000辆车，要从A到B,此时，若某人要改变，则他的行驶时间 2001/1

4、00 + 45 65，因此没人会改变,均衡：上下路上各2000 辆车； 对每辆车而言，对应回报为65,C,A,B,D,x/100,x/100,45,45,设想新修了一条快速路,注意，在没修这条路前，均衡中每人行驶时间是65 如果某人盘算改变为ADB，则他的行驶时间将变为45+4000/10080，于是他不会改变！,均衡是大家都走： ACDB 每人行驶时间为 4000/100+0+4000/100=80,布雷斯悖论,大家会做什么选择？,C,A,B,D,x/100,x/100,45,45,0,为什么大家不能像从前那样？,你会很合理地想走ACDB。也就是说，从前那样的模式在均衡态是不可能的（不均衡）

5、 你会这么想，其他人呢？会不会变成2000人走ACDB，另外2000人走ADB？,若你是决定走上面的 2000人之一，看到了这个局面，此时会不会有什么想法？,C,A,B,D,x/100,x/100,45,45,0,不同条件下：平时与车展时,平时，1000人要从A到B 车展时，4000人要从A到B,C,A,B,D,x/100,x/100,45,45,0,车展,公告：CD路段禁行,收费也可能是一种不错的机制,平时，1000人要从A到B，大家都走ACDB，很爽。车展时， 4000人要从A到B。,C,A,B,D,x/100,x/100,45,45,0,车展,公告：CD路段收费20元,假设人们认为花1元

6、钱省1分钟的时间是值得的,作业：均衡状态下走ACB，ACDB和ADB路线的分别多少人？各自花多长时间？,封路机制与收费机制的对比讨论,经济效益？社会效益？,C,A,B,D,x/100,x/100,45,45,0,车展,公告：CD路段禁行,公告：CD路段收费20元,辨析：布雷斯悖论（Braesss Paradox）,按照前面讨论的思路，多修一条路，人们出行状况反而可能变得更糟。那是因为：,出行的车辆更多了 因为新路很爽，人们倾向于都去走新路 新修的路比较窄 新的道路结构与人们的需求模式不适应了,在追求个人利益最大化动机的驱使下，解决社会问题不能仅靠增加资源，还要注意调整结构,经济基础 上层建筑,

7、生活中的其他例子？,生活中的布雷斯悖论：工作选择问题,10000,10000,100个员工，独立在T、R两种工作中选择一个（m+n=100），博弈均衡在哪里？,m,n,T,R,m = 50 n = 50 每人得200,生活中的布雷斯悖论：工作选择问题,10000,10000,15000,100个员工，T、R和T&R三种选择（m+n+k=100），选择T&R的人原来在T或R的份额要扣除。博弈均衡？,k？,k*100,k*100,m,n,T,R,T&R,可进一步深入探讨的问题（例）,对于任何交通网络，任何交通需求，是否都存在一种均衡状态？在均衡状态下的社会福利与社会最优之间有没有什么关系？ 除了交

8、通网络和前面分奖金的例子，还能举出什么现实生活中的例子，体现布雷斯悖论？,网络效应下的市场,学习目标： 理解具有网络效应产品市场的宏观行为特征，能完成在简单假设下均衡点周围的微观动态计算，能对产品推销的策略给予恰当解释,有些产品，有些活动，有些事务,如果最初只有很少人参加，基本会自生自灭 当参与人达到一定规模，则许多其他人也被吸引参与 这个成长的过程会继续到某个规模，然后基本保持不变,10,100人,1000人,10000人,“瓶装水”如何？其消费量的变化有这样的特点吗？ “登山运动”如何？参与活动的人群规模变化特点？ “微信”如何？使用人群规模的变化特点？ “自愿者”如何？参与自愿者服务的人

9、群规模变化特点？ “互联网搜索”如何？使用人群规模的变化规律？ “使用iphone”如何？ “使用Apple的演讲软件keynote”如何？ “上淘宝网”如何？ ,购买（采纳、参与）行为的两种基本动因,对产品内在价值的认识，因人而异 由购买同样产品的人群规模带来的价值放大（网络效应） 只有第一种动因的经济模型（无网络效应） 生产者和消费者之间的供需关系，均衡分析 包含两种动因的经济模型（包含网络效应） 多个均衡点（稳定的，不稳定的），市场动力学,r(x),f(z),r(x)f(z), p,r(x), p,r(x):内在价值，递减（安排） f(z):规模放大因子，递增（理当） 设r和f都定义在0

10、,1 gz(x)=r(x)f(z) 在规模z下个体x看到的综合价值 e.g. g0.7(x) g0.7(0.7)?,r(x)=1-x,f(z)=z,g0.7(x),x z,价值,特别关心一般的gz(z),r(x)=1-x f(z)=z gz(z)=(1-z)z 当规模为z时，个体z看到的综合价值,r(x)=1-x,f(z)=z,p*,考虑一个价格 p*,哪些人会觉得便宜，哪些人会觉得太贵,便宜,太贵,g0.6(x),感觉便宜的人较多,r(x)=1-x f(z)=z gz(z)=(1-z)z 当规模为z时，个体z看到的综合价值,r(x)=1-x,f(z)=z,p*,考虑一个价格p*,哪些人会觉得

11、便宜，哪些人会觉得太贵,便宜,太贵,感觉贵的人比较多,g0.6(x),在什么情况下，觉得便宜的人数恰好与设想的规模一致？,r(x)=1-x f(z)=z gz(z)=(1-z)z 当规模为z时，个体z看到的价值,p*,考虑一个价格p*0.25,z,z”,z，z”市场均衡点，自我实现的市场预期，self-fulfilling expectation,gz(x),gz”(x),z,z”,z是不稳定均衡点： 若市场规模在z点向下波动，则趋于离开z，并且越来越小； 若市场规模在z点向上波动，则趋于离开z，且不断增长； z”是稳定均衡点： 若市场规模在z”点向下波动，则趋于回到z”； 若市场规模在z”点

12、向上波动，则趋于回到z”；,上行动力 下行动力,作业,按照我们讨论采用的术语和记号，考虑一个有网络效应的产品。设人们对它的内在价值函数r(x)=1-x，用户群体规模的价值放大函数f(z)=z，定义域都是0,1。假设该产品的价格定在 p*=5/36。我们关心： 该产品的两个市场规模均衡点z和z” 假设在z均衡的情形，有10%的用户因某种原因流失了，下面哪些用户（x）也会觉得应该放弃该产品了。 假设在z”均衡的情形，有10%的用户因某种原因流失了，下面哪些用户（x）也会觉得应该放弃该产品了。,Q2： x=0 x=1/12 x=1/6 上述都不会,Q3： x=0 x=5/12 x=5/6 上述都不会

13、,这样的分析能给我们什么启示？,如果你创新了一种具有网络效应的产品 如果你的产品不具有网络效应,r(x),f(z),r(x)f(z),p*,z, z”,对于你的具有网络效应的新产品,尽快让用户量超过一个临界值（z），从而启动市场的网络效应。下面哪些措施可能是有效的？分别的针对性何在？,降低价格,限量免费赠送,提供独立功能,夸张广告,先降后提价,酒香不怕巷子深,降低临界值,提升用户量,独立价值降低价格,在网络效应下有可能呈现一种自然增长的市场（不断有先前认为“不值”的人们后来认为“值得”，从而成为用户）,r(x)f(zt-1) p*,zt xmax,创造 z0z1z2ze 的条件,预期 规模,实

14、际 规模,对于你的没有网络效应的产品,能否附加具有网络效应的功能？从而可以借助网络效应来扩大市场？,复印机传真机,一个示意性例子：读书会的改进,会员：交年费 得到的服务：参加定期举办的作者见面会 （假设你有本事将那些著名作者请来）,会员：交年费 得到的服务： 1.参加定期举办的作者见面会 2.向读书会1/4价出售旧书 3.1/4价买其他会员出售的旧书,可进一步深入探讨的问题（例）,前面谈到的布雷斯悖论和网络效应问题，都涉及到个人的回报与他人的参与有关，但有一点显著不同：前者中他人的参与对个人的影响是负面（消极）的，后者中则是正面（积极）的。 还有哪些现实中的问题可以从这个角度进行分类和研究？

15、例如，El Farol酒吧问题,小世界与大数据,学习目标： 透过近50年关于“小世界”的研究历程，体会到科学研究诸方法的效用，以及在大数据条件下计算与社会科学所能产生的深刻互动,小世界实验（Milgram，1967）,几百名初始者，要求每人通过转发，争取让一个指定的人收到一封信 向每个初始者提供了目标收信人的姓名、地址、职业等个人信息； 规定：参与者只能将信件直接发给相当熟的人，并请他继续转发。因此，如果一个参与者不认识目标收信人，则他不能直接将信寄给他； 结果，约三分之一的信件经过平均六次转发到达了目标。,在网上，从北大几步能走到清华？,北京大学 相关链接 研究生院院长联席会 国内大学 北京

16、 清华大学,新浪微博用户之间的路径,从我如何“走”到李开复？,几步可以到姚晨？,任志强呢，不能都这么近吧？,小世界问题的科学研究之路（1967-2015）,意识到这是不可思议的现象，且有意义 是普遍规律还是碰巧？（重复实验） 短路径的存在性是否社会网络特征导致的必然？（模型1） 短路径在短视搜索下的可达性意味着什么？（模型2，结构参数） 结构参数在现实网络中的体现？ 现实网络为什么会有那样的结构参数？ ,随机中的确定，偶然中的必然？！,小世界，是人类社会网络中的一个规律吗 ？,从现象到问题,社会网络中两节点间包含丰富的短路径！ 问题 这具有普遍（规律性）意义吗？ 为什么社会网络具有这样的性质？

17、它们源于社会网络的哪些基本原理？ 可以证明，完全随机的网络没有这样的性质 换句话说，能否依据社会网络的某些基本原理，说明这种性质的必然性？,形成社会网络的两种基本力量,同质性 亲属，邻里关系，同学，同事，共同兴趣 对应社会网络中的大量的“三角形”（圈子） 体现血缘或地缘等“亲近”关系 弱联系 偶然的原因，认识的“远程”朋友 对其所在的圈子并不一定熟悉,一种什么样的形式化网络，既体现这两种力量的作用，也便于我们分析其中是否有小世界现象？,Watts-Strogatz模型,一种抽象网络，节点有各自的空间位置，从而可谈两点间的距离，同时在互联结构上体现社会因素 意象：有许多“三角形”和少数随机的“远

18、程边”,想象大量节点排布成这种网格状,连接近邻:确定性，连接远程:随机性,每两点之间有一个网格距离,Watts-Strogatz模型（Nature,1998）,体现了同质连接和弱关系连接的概念，于是可以看成是现实社会网络的一个合理近似 从数学上可以证明：在这样的网络中，任意两点之间存在短路径的概率很高 弱连接的随机性将远程的节点“拉近”,从1967年到1998年，其间人们多次成功重复小世界实验，现在有了一个基于社会网络成因的解释。,但是，小世界实验带给我们的还有另一个层次的惊奇,社会网络上的短路径不仅是存在，而且仅通过短视搜索就可达！,但可以证明，在Watts-Strogatz模型上的短视搜索

19、导致长路径的概率很高。也就是说，该模型没法解释实验呈现出来的这种现象。 那么，有什么关键要素没有把握住（体现在模型中）？,回顾那个寄信（搜索）过程,每个人被告知：如果不认识目标人，就不能直接寄给他，但要有意识地转发，希望信件的下一站能离目标人近一些。,大量实验结果证明这样做是凑效的信件实际走了短路径说明现实社会网络结构支持这种做法,理论分析在WS社会网络模型上这样做效果不好信件走的路径很长说明该网络模型不支持这种做法,因此，需要一种社会网络模型,既反映任意节点对之间短路径的存在性，也支持在短视搜索方式下短路径的可实现性,网络中需要什么样的结构特征来体现这样的要求？,两个节点无论相距多远，都要有

20、机会很快接近； 两个节点的距离越近，存在直接连接的机会越大,Watts-Strogatz-Kleinberg模型,三个参数（r, k, q） r：同质性（邻近确定）连接的丰富程度 k：远程（随机）连接的个数 q：控制远程连接的概率随距离递减的强度,v,w,u,q取多少为好？,两个节点有一条弱关系边的概率与它们空间距离的某个幂次q成反比,不同q值对随机连接长度的影响,q值较小，随机边倾向于较远（对距离的“惩罚”小，远处的节点多带来的优势明显）,q值较大，随机边倾向于较近，连接远距离节点机会少了,Watts-Strogatz模型对应于q=0,该模型的最佳工作参数（q）,理论证明：当q=2时，短视搜

21、索达到最佳效果 计算仿真：由几亿个节点组成的网络中，考察不同的q值在分散搜索中的效果 对于这种规模的网络，在指数q介于1.5和2.0 之间时搜索效果最佳 随着网络规模的扩大，最佳的性能指数q越来越接近2,横轴为参数q，纵轴为从一个节点到达另一个节点所需的平均时间（跳步）,Nature 2000,可我们有了新的困惑,为了对“短视搜索建模”，WSK模型假设节点之间弱连接的概率随距离的幂次（q）递减，且当q=2时，短视搜索达到最佳效果。 但是，现实社会网络中，人们成为朋友的概率真的随距离递减，并且递减强度幂次q真的等于2吗？,这需要验证！,利用在线社会网络进行验证,大规模在线社会网络是否体现了这个（

22、Watts-Strogatz-Kleinberg）网络的特点？ 什么是需要验证的特点？ 在地理上节点均匀分布的社会网络中，两个人成为朋友的概率，与他们空间距离的平方成反比 如果是，则说明随机形成的社会网络可能具有某种本质的参数！ 但，在线社会网络如何体现这种地理关系？,LiveJournal（LJ），1999年建立的社交网站,来自LiveJournal的实验数据,50万用户，含邮政编码信息（地理信息）,但他们是不均匀分布的，不符合模型的假设，需要做一些“适配”工作,LiveJournal中用户的地理位置分布,考虑两人建立社会关系的概率，距离范围内的人数比距离具有更本质的意义,社会网络中结合地理

23、距离的节点相对排位,可以看成是节点在地理上均匀分布时区域范围概念的一种推广，“排位”与“距离”有对应关系 这就使我们能一般性地处理节点在地理上分布不均匀的问题了,v,w,这样,要验证的是 在均匀地理分布情形，一个节点与某一距离上的节点成为朋友的概率随距离的平方递减（1/d2） 此时等价于要看 一个节点与在某一相对排位上的节点成为朋友的概率随排位递减（1/r）,近乎完美的验证！（PNAS, 2005）,真实社会网络的测量参数与模型最优参数相当吻合！,这意味着，大量微观社交关系的建立总体上呈现一种最优化特征，或者说大量人群的随机社会活动相当于一台计算机，完成了一种优化计算（实现了最优参数）这可以看

24、成是社会计算的一个实例，也是体现社会系统中微观与宏观关系的实例！,关于“小世界”问题的研究是否就完结了？,No！ Kleinberg在他的模型上证明的q=2是最优的，后面有人用大型社交网数据验证了这个结论。,只是说明了模型的有效性,但是，人们随机形成的社交网，为什么就“实现了”这种宏观的最优呢？ Zhi Yang and Wei Chen, “A Game Theoretic Model for the Formation of Navigable Small-World Networks, WWW Conference 2015,杨智和陈卫（W3C15）工作的基本思想,将人们的交友看成是一个

25、博弈 策略：选择与一定距离上某人交友的概率 在幂律基础上，确定参数（q） 回报：在一定距离（平均）上也被选择交友的可能性 证明了：最稳定的纳什均衡出现在q=2。,“小世界”问题的科学研究之路,实验现象 (1967),理论模型 (1998),模型改善(2000),根源探究 (2015),测量验证 (2005),重复实验 (),what,how,how & “must be q=2”,confirm,why,作业,我们已经知道，“小世界”是一个社会现象（规律）。在关于小世界近50年的研究历程中，人们用到了实验设计、数学模型、计算模拟（仿真）、数据验证等方法和手段。试概述小世界研究的历程，并特别指出各种方法手段在其中的作用。,可进一步深入探讨的问题（例）,小世界数学模型的证明？ 小世界问题的大数据验证的方法细节？ 人与人之间的“社会距离”，除了用地理位置空间距离或者距离之间的人数来定义外，还有没有其他合理的定义？在那样的定义下如何验证小世界现象？,社会科学中的计算思维浅赏,网络中的博弈,小世界与大数据,用计算思维的方法观察分析经济社会现象，会使我们更加热爱科学，热爱生活。,网络效应下的市场,2013年秋，作为北京大学首批慕课之一，这门课开出了一个慕课版本，同时结合慕课