互联网地图

从这里
拍摄 大家好!

我想向您介绍互联网的地图或集群超过35万的网站按照用户之间导航的结果。国籍和所在地在地图上 - - 圆的大小是由网站的访问量,颜色决定了它链接到其他网站。如果两个站点之间有用户源源不​​断,那么他们将“尝试”贴近对方。当该算法完成时,地图可以看出簇位点(簇状物)一般的用户都统一。

269​​45826



例如,如果你在搜索habrahabr.ru类型,我们可以看到,dirty.ru和leprosorium.ru在同一个“星座”,但走livejournal.ru。这表明,那些谁是阅读本书,并访问这些网站(相对于课程的平均俄罗斯互联网用户)的概率较高。

集群的一个更有趣的例子可以看出,在地图的底部,日本和紫色黄色的巴西之间:有一整pornostrana大小与所有Euronet上具有可比性。有趣的是,作为在这个问题上能力不够,内部有大量pornoklastera可以区分主题的子集群较小。

对于那些有兴趣在简要技术说明 - 欢迎下切

工程部分

整个项目是用C#编写,并且由三部分组成:群集的程序,该程序生成的瓷砖和网站。每一部分都值得特别的考虑,如果有兴趣,我可以再告诉我们更多关于他们。

dc3eda8ea3.jpg

基线数据来自Alexa的收集,他们代表出席,上游和下游用户转变的记录(上游 - 他们来自哪里,下游来了 - 在这里做了)。标准化后,我们得到一个加权无向图的顶点和35万超过200万。肋骨。

计数这个图 - 一个复杂的计算问题,所以它是由该GPU特殊模块,但幸运的是他没有必要。经过一个棘手的优化受骗都花了几个星期的一个强大的连续工作,但仍然是一个家用熨斗。

讲简单地说,该算法是在根据作用于他们的地图的增量位点。许多用户的转换 - 强大的力量试图汇集的场所;如果站点距离太近,它会启动排斥力,等等。更多细节,可以在这项工作中reports-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf找到

主要的问题是该算法的巨大计算复杂性。解决问题的“头”,在每个步骤后必须计算力的叠加为每个站点,即:计算功率为每对站点,和周围器122十亿这样的对。(很好的一步,对吧?)。因此,举行了坚韧和全面优化的算法并行化。幸运的是.NET平台对于这样的娱乐出奇的好。

第二步骤是瓷砖的产生。瓷砖 - 一个小图片256×256像素,使得在谷歌地图,Yandex的和其他服务的地图的图像。在一般情况下,没有什么复杂的 - 产生大图片,切​​成所需大小的正方形,企业不知。但是,这些图像是近30亿美元。即使只是为了拷贝或删除与瓷砖在Windows目录需要两天的时间。而将其倒入托管一个单独的问题。

第三阶段 - 发动机配合谷歌地图,把拼在一起,并得到它来显示地图。这里,在一般情况下,没有什么困难,虽然有与突起和卡的定位一些困难。

最后一个阶段 - 托管和发行的选择。在这里,它并非没有冒险。现在,它变成了亚马逊的云计算和它是更容易,更便宜,比我想象的。

在一般情况下,我已经积累了一些经验,我会很高兴与尊重的社区共享。当然,在一般情况下,没有什么特别的,哈布雷真的很有趣的项目和琐碎的解决方案,不过,我认为,许多人来说,可以很有趣。

我也期待着任何想法,评论,批评 - 任何反馈!

资料来源:

标签

另请参见

新&值得注意