Matches in ScholarlyData for { <https://w3id.org/scholarlydata/inproceedings/www2012/paper/1078> ?p ?o. }
Showing items 1 to 15 of
15
with 100 items per page.
- 1078 creator chin-wan-chung.
- 1078 creator jaimie-y-park.
- 1078 creator jungmin-lee.
- 1078 creator min-joong-lee.
- 1078 creator ryan-h-choi.
- 1078 type InProceedings.
- 1078 label "QUBE: a Quick algorithm for Updating BEtweenness centrality".
- 1078 sameAs 1078.
- 1078 abstract "The betweenness centrality of a vertex is defined as the number of shortest paths that go through the vertex, divided by the number of all shortest paths in a graph. Betweenness centrality is widely used in network analyses. Especially in a social network, the recursive computation of betweenness centrality of vertices is performed for the community detection and finding the influential user in the network. Since a social network graph is frequently updated, it is necessary to update the betweenness centrality efficiently. To the best of our knowledge, this is the first work that proposes an algorithm which updates the betweenness centrality of all vertices in a graph efficiently. When a graph is changed, betweenness centerality of all vertices should be recomputed from the scratch using all the vertices of the graph. In this paper, we propose a method that efficiently reduces the search space by finding a candidate set of vertices whose betweenness centrality can be updated and computes their betweenness centeralities using candidate vertices only. As the cost of calculating betweenness centrality mainly depends on the number of vertices to be considered, the proposed algorithm significantly reduces the cost of calculation. Experiments on large datasets show that our algorithm outperforms an adapted existing algorithm in updating the betweenness centrality of vertices.".
- 1078 hasAuthorList authorList.
- 1078 isPartOf proceedings.
- 1078 keyword "Algorithm".
- 1078 keyword "Betweenness centrality".
- 1078 keyword "Graph theory".
- 1078 title "QUBE: a Quick algorithm for Updating BEtweenness centrality".