NCM简介.ppt

与受限买家关联的卖家调整价格 形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组 7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4 1 1 0 1 0 1 与受限买家关联的卖家调整价格 形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组 7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4 2 1 1 2 0 2 与受限买家关联的卖家调整价格 形成新的偏好卖家图（看到边的调整），此时已经没有受限组?存在完美匹配 7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4 3 1 1 2 0 3 匹配市场中的计算：启示 我们看到 市场经济中的一些基本概念： 理性的人、价格、供需关系、物以稀为贵、均衡、社会最优，… 通过一个简单的模型： 匹配市场（偏好卖家图、根据受限组进行价格调整，…） 得到了生动的表达。 而一旦这么做了，也隐含着一个计算问题的高效解决（市场机制扮演了一个高效的问题求解器的角色！） 社会计算、跨学科计算思维的一个具体示例 大数据与小世界 小世界实验（Milgram,1967） 几百名初始者，要求每人通过转发争取让一个指定的人收到一封信； 向每个初始者提供了目标收信人的姓名、地址、职业等个人信息； 规定：参与者只能将信件直接发给能叫出名字的熟人，并请他继续转发。因此，如果一个参与者不认识目标收信人，则他不能直接将信寄给他； 结果，约三分之一的信件经过平均六次转发到达了目标。（“六度分隔”） 在网上，从北大如何到湖州师范学院？ 北京大学 ? 相关链接 ? 研究生院院长联席会 ? 国内大学 ? 浙江 ? 湖州师范学院 距离＝5 如何从湖州师范学院到北大？ 湖州师范学院 ? 高校链接 ? 浙江大学 ? 图书馆 ? CALIS ? 高校特藏资源 ? 北大博文 ? 北京大学图书馆 ? 北京大学 距离＝8 从这个例子我们可以体会到 Web信息总体可以看成是一个有向图 网页为节点，网页中的超链接为有向边 这个有向图似乎具有“小世界”的特征 任意两个节点之间存在短路径的可能性很大 这样的短路径常常是可以由基于局部信息的“搜寻”找到的 微博、人人等在线社交网络，节点和边的含义不同，但也有类似的结构性质。 在新浪微博上，从“北京大学李晓明”几步能走到“姚晨”？ 有理由相信：新浪微博也是一个“小世界” 探讨随机中的确定，偶然中的必然 小世界是人类社会网络的一个规律性现象吗 ？ “小世界”的研究之路 Milgram（米尔格拉姆）的实验（1967） 第一个惊奇：六度分隔！ 第二个惊奇：那些信居然能沿短路径到达！ Watts-Strogatz的社会网络模型，对第一个惊奇给予了解释（1998） Watts-Strogatz-Kleinberg模型，对第二个惊奇给予了解释（2000） W-S-K模型在大规模OSN（大数据）中得到验证（2005） 理论解释 测量验证 实验现象 Watts-Strogatz模型 定义一种图（网络），体现上述因素 有许多“三角形”和少数随机的“远程边” 想象大量节点排布成均匀网格状 连接近邻:确定性，连接远程:随机性 每两点之间有一个网格距离 Watts-Strogatz模型（1998） 体现了同质连接和弱关系连接的概念，于是可以看成是现实社会网络的一个合理近似 可以证明：在这样的网络中，任意两点之间存在短路径的概率很高 弱连接的随机性将远程的节点“拉近” 因此，需要一种社会网络模型 既反映任意节点对之间短路径的存在性，也支持在这种转发方式下短路径的可实现性 网络中需要什么样的结构特征来体现这样的要求？ 两个节点无论相距多远，都要有机会很快接近； 两个节点的距离越近，存在直接连接的机会越大 网络中的博弈 市场中的计算 大数据与小世界 社会科学也需要计算 社会现象中蕴含着计算 理解社会过程有助于计算科学的发展 国关中的计算 要点：关注计算与其他专业的交界面 对于计算机专业，理解其他学科与计算的交界面，而不是要成为其他学科的专家 对于非计算机专业，以计算的观点理解有关过程，而不仅是掌握计算工具 早期引入，而不是晚期分流 * 康奈尔大学 * 斯坦福大学 * 剑桥大学 * * * 如果我们关心某些因素，则应该将它们纳入到收益中考虑。 * * 设最初上