圖計(jì)算算法應(yīng)用舉例-pagerank

1examplesCollaborativefiltering:ALS,SGD,NMF.Clustering:K-means,spectralclustering.Topicmodel:LDA.Machinelearning:SVM,BP.GraphMining:PageRank,ConnectedComponents,TriangleCounting.2pagerank3WebgraphdatagraphVertexpageEdgelinkVertexdataREdgedataweightoflinkPagerankupdate()獲取頂點(diǎn)所有入邊值之和計(jì)算pagerank值并更新頂點(diǎn)值更新該頂點(diǎn)所有出邊Graphchi_PageRankupdate(v)

//Computesumoverinedgesvaluessum=0

foreach(ein

inedge(v))):sum=e.data//UpdatethePageRank

pagerank=0.15+(1-0.15)*sum

v.set_data(pagerank)//updateoutedgesvalues

edgevalue=pagerank/v.num_outedgesforeach(einoutedge(v))

e.set_data(edgevalue)5164235updateInedgee1Inedgee2e1e2Σ(,)0.15+0.85*pagerankpagerank/n1outedgee3Outedgee4Graphchi實(shí)現(xiàn)pagerank的update函數(shù)6void

update(graphchi_vertex<VertexDataType,

EdgeDataType>

&v,

graphchi_context

&ginfo)

{

float

sum=0;

if

(ginfo.iteration

==

0)

{//第一次迭代，賦初始值

for(int

i=0;

i

<

v.num_outedges();

i++)

{

graphchi_edge<float>

*

edge

=

v.outedge(i);

edge->set_data(1.0

/

v.num_outedges());//每條邊，賦初始值1.0/出邊數(shù)

}

v.set_data(0.15);

//每個(gè)頂點(diǎn)，賦初始值0.15

}

else

{

for(int

i=0;

i

<

v.num_inedges();

i++)

{

float

val

=

v.inedge(i)->get_data();

sum

+=

val;

}

float

pagerank

=

0.15

+

(1

-

0.15)

*

sum;

//計(jì)算頂點(diǎn)的pagerank值

if

(v.num_outedges()

>

0)

{

float

pagerankcont

=

pagerank

/

v.num_outedges();

for(int

i=0;

i

<

v.num_outedges();

i++)

{

graphchi_edge<float>

*

edge

=

v.outedge(i);

edge->set_data(pagerankcont);

//更新出邊的值

}

}

ginfo.log_change(std::abs(page