大图的随机游走( 个性化 PageRank ) 算法

・2 分钟阅读

  • 源代码名称: bidirectional-random-walk
  • 源代码网址: https://www.github.com/plofgren/bidirectional-random-walk
  • bidirectional-random-walk的文档
  • bidirectional-random-walk的源代码下载
  • Git URL:
    git://www.github.com/plofgren/bidirectional-random-walk.git
  • Git Clone代码到本地:
    git clone https://www.github.com/plofgren/bidirectional-random-walk
  • Subversion代码到本地:
    $ svn co --depth empty https://www.github.com/plofgren/bidirectional-random-walk
                              Checked out revision 1.
                              $ cd repo
                              $ svn up trunk
              
  • 双向随机游走,

    存储库包含一个双向随机游走(个性化PageRank )估算法,算法在个性化PageRank估计和搜索中得到了描述: 一种双向方法,更全面的在博士学位论文中。

    例如,我们将在/src/test/resources/test_graph.txt.中的小图中使用传送概率0.2来计算节点1和2的分PPR数。 首先安装java,sbt和git。然后运行

    
    git clone https://github.com/plofgren/bidirectional-random-walk.git
    
    
    cd bidirectional-random-walk
    
    
    sbt console
    
    
    val graph = co.teapot.graph.ConcurrentHashMapDynamicGraph.readGraph("src/test/resources/test_graph
    
    
    .txt")
    
    
    val estimator = new soal.ppr.BidirectionalPPREstimator(graph, teleportProbability=0.2f)
    
    
    estimator.estimatePPRSingleSource(0, 1)
    
    
    estimator.estimatePPRSingleSource(0, 1, relativeError=0.01f) // For greater accuracy
    
    
    
    

    我们的算法也可以从源节点而不是单个节点上的分布开始。例如,如果我们想要使用从节点0开始的概率为0.8且节点2的概率为0.2的随机游走来估计PPR分数,我们可以运行,

    
    val sourceDistribution = new soal.util.DiscreteAliasSampler(Seq(0, 2), Seq(0.8f, 0.2f))
    
    
    estimator.estimatePPR(sourceDistribution, 1)
    
    
    
    

    库使用Tempest图形库支持大图,它提供了基于内存映射文件的高效图形实现。

    讨论
    Fansisi profile image