f*******4
发帖数: 64 | 1 最近在做一个 social network data analysis 的项目
我自己想的算法效率很低，跪求大神指教。。
一个超大的txt文件（4G吧）(ID有10^6个，edge有10^8个)
全部是如下格式：
1 5
1 6
2 7
1 7
都是无序的。。这些ID
数字代表ID，我要做的是找出一个概率P（分数）： （A->C）/(A->B , B->C)，也就是
传递性，找到这个txt里 三角形（传递关系）的概率
比如，如果这个txt里只有1、5、8、9、2、6.
1 5
5 8
5 9
1 8
2 6
1认识5,5认识8,1认识8,；1认识5,5认识9,但1不认识9。 这个P就等于0.5。。（A->C）
/(A->B , B->C)（因为2、6无法和另一个ID产生关系，因此不要）我的target就是要求
出这个P。。
因为这些ID肯定都是long型，然后edge估计有个N*10^8,我不确定是否可以用内存（我
们服务器内存15Gb）。
目前，我是这么做的：把这个大txt，按ID的除余，分成0-19999两万个hash txt，然后
操作，这种做I/O明显是很大的，然后处理，又因为无序性，我每次很naive的线性找，
，然后就越来越慢了。。
问问大家，有没有好办法解决。
还有个问题就是说，有的数据集是undirected，有的是directed。按照要求，我得把所
有的directed转换成undirected，所以比较麻烦。 | b********e
发帖数: 58 | 2 import the data into a graph database such as Neo4j, rest is just call their APIs. | l**a
发帖数: 423 | 3 你能具体点要什么样的结果么？每个node的指向其他node的概率？
传递链长的话，是不是会有1／3，1／4，1／5，，，， ？
你得node才1million，根据你要的结果，使用正确的graph data structure，内存应该
是够用的。
另外这个题看起来不像是一个project，更象是一个challenge。 |
|
