《六度空间的应用.docx》由会员分享，可在线阅读，更多相关《六度空间的应用.docx（27页珍藏版）》请在三一办公上搜索。
1、”六度空间”的应用找出两个陌生人之间的关系（一）前几日在人人网上看到有位北京大学的做了一个人人网六度空间的Flash,觉得很好玩，遂向其请教一二，自己也做了一个，这篇就来 做个梳理和总结吧，哪些性能方面不好的希望大家能够指出并改进.本篇没有完整的代码或程序可以下载，更没有我获取到的数据可以下载, 数据也很大，我用XML存储了我们学校整个人际关系用了几百兆！切勿用文章内的思路做盗取他人隐私违法犯罪的商业应用！六度空间可行性分析六度空间”理论又称作六度分隔（Six Degrees of Separation）理论。这个理论可以通俗地阐述为： 你和任何一个陌生人之间所间隔的人不 会超过六个，也就是说
2、，最多通过六个人你就能够认识任何一个陌生人。该理论产生于20世纪60年代，由美国心理学家米尔格伦提出。输入一个人A,找到另一个人B,通过在线联网的方式（本地不保存数据）找到A和B之间的关系那当然好，但在人人网没有提供一个能快 速找到任意一个人的好友的API情况下做到这点几乎是不可能的（时间方面）.我做了一个测试，如果一个人有1000个好友，在120kbps的网 速下找到他的所有好友大概需要8s钟！可想而知，你想找出A和B之间的关系，采用双向搜索自然来得快不少，先找A所有的好友，再找B 的好友，看看有没有交集.没有继续找A所有的好友的好友，找B所有的好友的好友，看看有没有交集到这一步需要的时间地
3、球大概已经 转了半圈了，我昨晚找了 C的好友，再找C的好友的所有好友，从早上1:58找到早上6:01.所以我说这么多意思是没有快速API的情况下 做成在线版几乎不可能，除非你本地保存了数据，说着A和B是直接好友关系.那么就下载所有人人网用户的信息?人人网有近2亿账号，如果每个只需要5秒的话，对于我这个带宽120kbps,硬盘250GB的电脑显 然也不可能那么就从小范围做起吧，就找出我们学校所有人之间的关系吧.得到学校里每个人，以及每个人的好友假设学校里的每个人都注册了人人网（对于那些没有注册人人网的俺也没法找到他们，呵呵），我偶然想到了一个特殊的人人网用户A, 这个用户是学校一个聊天论坛在人人
4、网里的一个账号，好友数量已经达到2000,我有如下假设：任何一个学校里的人B, 一定有一个他认识 的人认识A,按照人人网里的话说叫做A和B有共同好友，这个假设根据我个人经验认为是正确的，如果B不满足这个条件，这个人一定孤 陋寡闻，不参加社交-_-!所以找到学校里每一个人，可以以这个A为起点，找到A的所有好友集合S1,再找到S的所有好友，那么整个学校的人的名单90%以上 已经到手.在昨天那个月黑风高的夜晚，我整整用了 4个小时把学校所有人都下载下来了（大概15W条记录）.存储人和人之间的关系光下载到到人的名单还不行，我并不想以A为中心建立大家之间的关系，因为A毕竟是一个组织，不是一个人，以它为中
5、心的关系几乎 都是浮云，现在已经有A的所有好友，以及A的好友的好友集合S2sa, sb, sc.,学校的所有人都包含在S2中了，任何人之间的关系可以 用图表示，在人人网中且是无向图（没有A是B的好友，B不是A的好友这种情况），所以还得再逆向的找出S2中的每个人的好友，并存储这 个关系！图可以用矩阵法和邻接表表示，因为这个关系图属于稀疏矩阵，应该用邻接表表示更省空间（用矩阵表示也是几乎不可能的事情，因为 如果有学校有10000个人，那么就得建立一个10000*10000的矩阵，当然可以利用矩阵的一些运算比如找出矩阵特殊值等方法压缩这个矩阵, 但压缩之后的矩阵仍然不小.）.因此我建立了如下一个XM
6、L格式的文件存储人和人之间的关系.1234Relations56789101112这个把全校所有人都爬虫出来的代码是这样的，先找出A的所有好友:public void downLoadData()1 (23456789101112131415XmlDocument doc = new XmlDocument();doc.Load(矿C:UsersChen HuaDesktopRelation.xml)；renrenoperation renren = new renrenoperation();Console.WriteLine(Login Success);/获得A的好友var people
7、List = renren.Get_FriendList(A 的 id 号码)；foreach (Person person in peopleList)(var node = doc.CreateElement(Person);node.SetAttribute(id, person.id);node.SetAttribute(name, person.name);node.SetAttribute(school, person.school);node.SetAttribute(faceUri, person.faceUri);1617181920212223242526272829303
8、13233 doc.DocumentElement.AppendChild(node);var list2 = renren.Get_FriendList(person.id);Console.WriteLine(person.name + Write Success.);/获得A的每一个好友的好友foreach (Person person2 in list2)(if (person2.school.Contains( 某某学校)| person2.school.Contains( 南京市”)(var friend = doc.CreateElement(Friend)；friend.Set
9、Attribute(id, person2.id);friend.SetAttribute(name, person2.name);friend.SetAttribute(school, person2.school);friend.SetAttribute(faceUri, person2.faceUri);node.AppendChild(friend);static(void Main(string口 args)12345接下来就是把A的好友的好友提取出来，找出A的好友的好友的好友.（逻辑有点那个.不知道大豕有没有想通）XmlDocument doc = new XmlDocument(
10、);doc.Load(矿C:UsersChen HuaDesktopRelation.xml)；Console.WriteLine(XML 加载完毕.);var PersonList = doc.SelectNodes(/Person)； /所有的 Personforeach (XmlNode EveryPersonNode in PersonList) /Person 中所有的节点foreach (XmlNode EveryPersonChildNode in EveryPersonNode.ChildNodes) /每个 Person 的子节点, 朋友(if (ContainedThisP
11、erson(EveryPersonChildNode, PersonList)/如果发现这个朋友已经在Person集合中( else/如果不存在(var NewPersonNode = doc.CreateElement(Person)；/新建一个节点NewPersonNode.SetAttribute(id，EveryPersonChildNode.Attributesid.InnerText);/设置 id,名字，学校，头像等NewPersonNode.SetAttribute(name， EveryPersonChildNode.Attributesname.InnerText);New
12、PersonNode.SetAttribute(school， EveryPersonChildNode.Attributesschool.InnerText);NewPersonNode.SetAttribute(faceUri， EveryPersonChildNode.AttributesfaceUri.InnerText);(/开始加载这个节点有哪些朋友foreach (XmlNode AnotherPersonList in PersonList)foreach (XmlNode AnotherPersonListChildNodein AnotherPersonList.Child
13、Nodes)if (AnotherPersonListChildNode.Attributesid.Inn erText = NewPersonNode.Attributesid.InnerText)78910111213141516171819202122232425262728293031(333435363738394041424344454647484932var newFriendNode =doc.CreateElement(Friend)；newFriendNode.SetAttribute(id，AnotherPersonListChildNode.ParentNode.Att
14、ributesid.InnerText);newFriendNode.SetAttribute(name，AnotherPersonListChildNode.ParentNode.Attributesname.InnerText);newFriendNode.SetAttribute(school，AnotherPersonListChildNode.ParentNode.Attributesschool.InnerText);newFriendNode.SetAttribute(faceUri，AnotherPersonListChildNode.ParentNode.Attributes
15、faceUri.InnerText);NewPersonNode.AppendChild(newFriendNode); break;doc.DocumentElement.AppendChild(NewPersonNode);Console.WriteLine(Add New Node +NewPersonNode.Attributesname.InnerText);doc.Save(矿C:UsersChen HuaDesktopRelation.xml)；private static bool ContainedThisPerson(XmlNode node, XmlNodeList no
16、deList)(foreach (XmlNode nodeInList in nodeList)(if (node.Attributesid.InnerText = nodeInList.Attributesid.InnerText) return true;return false;上面说了那么多，怎么获得好友列表呢？1. 分析登陆协议，看登陆时POST 了哪些信息，写一个登陆方法2. 去 20 位）&id=你需要找的 id获得第2步每一页的字符串，用正则表达式提取出好友的信息，正则表达式我写好了：imgsrc=(a-zA-z+:/s?(.*)v/as+v/dds?.*s?vdt.*v/dt
17、s?vdd(.*)v/dd是一个获取好友列表的测试图片:先写这么多，程序还在哗啦啦的运行中，下篇继续争取多一些程序优化方面的.3-J诚M 念 4# V 爆0口41 32eamSEBxnrrNS格峪JDSOM用K订AMjslM*t2.s.埋B*u.i.aBtnMAMnskAEuMAaflIl.G.理d7AMP iMT&ujE!niflT，eSAM.SMM* 沮lR* “ 昌xwBKlEMiimmax3JBEh1E3ufi耳5胤 IBAflMI B21flxflllJL.Jxj&fifluKnxlfchJMJkxfi酉flB*#ALray.?.iwM.m，ffiLEz E牌AllzEuE 出貌.E
18、:fiJL急焦恩0 &JC 三短HaEflcJftDflM4B fixaF 思- u 巳景aMMExK知lMAaELsu sMHHuyiMAaMfi n.0.一 H看里zxM4mdlAmas*3芸 m -Be-lsJP- M,* 音 AaB* La 耳匹 ias 星Ex 闩XJMamEafiM A4&AM皇Bei.43aaBlal4ElM.alHlB ExBaJDa&30 -*flDfiaMA出X屈f xvxA*i心归!二4BalKE1xk M2=xss5-Aa，宙afi-ckNS u职3MBX#ZU雪一LBx&mH9xwuz MaBAsxmMnEfiBBfixKB3ABnK*鸟群城iHv4-
19、agM2flEUaKaAa fiaft&Mnls星M3_ Jrsdi写* ! *XS.XITMK CM Lai匚 MZaL箜 rauEJn 5 eixMa与Ma5M3.utMpflBfili3EIs谢 &KuliMHa爆八砖amkx 盘 Ajsni AQy.Q与 e 4LxwtB里&3患AHailfiMnMa* a瞬*EarBaM 辱K曲l.pLLmB虹aEj 邕二Mw 晟liibi里5IxTaEfl蛆xkbk七-&言 gmanAfM wAalJUAl;虫 JjlIlllaE2am 叫HZA版 GJMysm mAMAiLxxMnnB区KaslflJ&Jxa六度空间”的应用一找出两个陌生人之间的
20、关系（二）哎，熬了好几个夜，掉了好多根头发，终于接近完工，如果真的要拿给别人用还需要修补很多东西.先发几张程序运行的图片吧:）第一张是找出两人关系，我试了很多人，几乎都只需要通过一个人就能找到另一个人，第二张是寻找XML文件中某个人有哪些好友.存储内容的改进在写上篇博客的时候程序一直在运行（在保存人和人之间的完整对应关系），我估算还需要好几个小时才能停下来，所存储的XML文件也会大的惊人，估算达到1GB以上，其实运算之前这个时候的XML中已经包含了所有的人，只不过暂时是一种类似有向图（A是B的好友，B不是A的好友）的关系，现在运算的也只是把有向图的关系完全拓展开，变成无向图（A是B的好友，B也
21、是A的好友而已）.在发现完整 关系的情况下，存储所需要的空间如此之大时，我放弃了这种方法.在下载完所有人的头像照片（4万多张）后，我把XML中每个节点的 school和faceUri删除掉了，这样存储人与人的关系只用了 15.8MB.现在的存储结构如下： Relations2345678910Person id= :Friendid= name=/id= name=/11 12 /Relations从这个XML中通过一些XML的操作方法可以就可以得到很多信息了.RelationOperate 类1.每次定义一个RelationOperate类，需要传进一个XML文件地址，以对它进行操作priv
22、ate XmlDocument xmlDoc = new XmlDocument();1234public RelationOperate(string xmlDocPath)(xmlDoc.Load(xmlDocPath);2.通过一个id找到他的好友列表/123456789101112131415161718192021222324/获取一个id的好友/ / 要查找的 id/ 该 id 的好友 id 列表/returns public List getFriend(string id) (List friendList = new List();var PersonList = xmlDo
23、c.SelectNodes(/Person)； 所有的 Person 节点 foreach (XmlNode xmlNode in PersonList)若果Person节点已经包含了该id的用户 if (xmlNode.Attributesid.InnerText = id) (/则增加这个Person节点的每一个子节点到friendList中 因为他的每一个子节点都是他的好友foreach (XmlNode node in xmlNode.ChildNodes)friendList.Add(node.Attributesid.InnerText); return friendList;上面
24、的条件不满足时，就查找哪些Person的子节点(朋友)里边包含这个id foreach (XmlNode xmlNode in PersonList)foreach (XmlNode node in xmlNode.ChildNodes)(if (node.Attributesid.InnerText = id)(25friendList.Add(xmlNode.Attributesid.InnerText);26break;272829return friendList;303.获取一个id的姓名123456789101112public string getName(string id)(
25、var PersonList = xmlDoc.SelectNodes(/Person)； 所有的 Person 节点foreach (XmlNode xmlNode in PersonList)若果Person节点已经包含了该id的用户if (xmlNode.Attributesid.InnerText = id)(return xmlNode.Attributesname.InnerText;上面的条件不满足时，就查找哪些Person的子节点(朋友)里边包含这个id_ _ . _ 一string name ;foreach (XmlNode xmlNode in PersonList)fo
26、reach (XmlNode node in xmlNode.ChildNodes)13(14if (node.Attributesid.InnerText = id)15(16name = node.Attributesname.InnerText;17return name;181920return name;214.获取一个姓名的id号码123456789public string getID(string name)(var PersonList = xmlDoc.SelectNodes(/Person)； 所有的 Person 节点 foreach (XmlNode xmlNode
27、in PersonList)若果Person节点已经包含了该id的用户if (xmlNode.Attributesname.InnerText.Contains(name)(return xmlNode.Attributesid.InnerText;上面的条件不满足时，就查找哪些Person的子节点(朋友)里边包含这个id10foreach (XmlNode xmlNode in PersonList)11foreach (XmlNode node in xmlNode.ChildNodes)12(13if (node.Attributesname.InnerText.Contains(nam
28、e)14(15string id = node.Attributesid.InnerText;16return id;171819return null;205.获取两个id之间的关系（广度优先）1234567public List getRelation(string A, string B) (/A直接认识B 0层关系var Afriend = getFriend(A);List relation = new List();foreach (string id in Afriend)if (id = B)(910111213141516171819202122232425262728293
29、03132relation.Add(A);relation.Add(B);return relation; /A的好友是B的好友1层关系var Bfriend = getFriend(B);foreach (string friendA in Afriend)foreach (string friendB in Bfriend) (/A的某个朋友也是B的某个朋友 if (friendA = friendB) (relation.Add(A);relation.Add(friendA);relation.Add(B); return relation;/A的好友的好友是B的好友2层关系List
30、AFriendFriend = new List();foreach (string friend in Afriend)(if (friend != B)/涉及两层关系时，A的Friend不直接是B(FriendFriend ff = new FriendFriend();34353637383940414243444546474849505152535455565733ff.parent = friend;ff.friend = getFriend(friend);AFriendFriend.Add(ff);foreach (FriendFriend ff in AFriendFriend
31、)(foreach (string friend in ff.friend)/涉及两层关系时,A的Friend的Friend不直接是Bif (friend != A)(foreach (string friendB in Bfriend)(/B的朋友也不直接是A, B的朋友也不直接是A的朋友 if (friendB != A) & (friendB != ff.parent) (if (friend = friendB)(relation.Add(A);relation.Add(ff.parent);relation.Add(friend);relation.Add(B);break;retu
32、rn relation;5859606162涉及3层关系 A的好友的好友C是B的好友的好友63/C 定是那个种子节点64/还没写3层关系65return relation;66结合上边的类操作已经保存好了的XML,可以用WPF或者其它做出一些找关系的程序，在自己的网站上加上这么一个功能，很绚丽的哦.另外我还发现应该用手机人人网的协议接口，那个页面下载的内容精简，没有很复杂的CSS, Javascript等等，以后真正要做出应用的话应该研究手机版的协议.本文也只是提供一个思路，可以做出一个这个东西.另外真正了解六度空间的威力也是很好的，如果一个产品被20个人看到，每个人推荐给了另外的20个人循环下去，这个对产品的推广是十分有好处的.当下很多东西正是基于六度空间的这个 理论，用户群变得超级庞大.
