Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Scalable computational techniques for centrality metrics on temporally detailed social network
Gunturi V., Shekhar S., Joseph K., Carley K. Machine Learning106 (8):1133-1169,2017.Type:Article
Date Reviewed: Feb 15 2018

To analyze social networks, where social interactions change over time, special graphs and methods are needed. In this paper, social networks are represented as temporally detailed (TD) networks; the aim is to compute centrality metrics on them, betweenness in particular. At the basis of those metrics, there is the need to compute the shortest path between a pair of nodes, a problem that presents computational challenges in such dynamic and very large networks.

The authors propose a new algorithm, called EBETS, based on the novel idea of reducing the number of re-computations by defining epoch points, the time points where the metric of the shortest path changes. Those points are computed using a lazy approach and a new data structure, the TD priority queue, in conjunction with a path function that represents the total cost of the path as a function of time.

EBETS is demonstrated to be correct and complete. Space and time complexities are studied for a heap-based implementation; the advantages of EBETS with respect to other methods are in reducing the re-computations more than the asymptotical complexity. Experimental evaluations on three datasets analyze the effect of different parameters; taking Djikstra’s algorithm as the baseline, EBETS consistently performs better.

The proposed method is promising, and, besides computing betweenness, it can easily adapt to compute other extensions.

The paper is not always easy to follow, as it makes many lateral considerations and comparisons with other approaches. Unfortunately, the authors do not provide much of the implementation details. However, the reader is guided through many examples to understand how the algorithm works.

For readers interested in the application side, the three real datasets do not add much to a paper that substantially presents an algorithm.

Reviewer:  G. Gini Review #: CR145858 (1805-0259)
Bookmark and Share
  Featured Reviewer  
 
Dynamic Programming (I.2.8 ... )
 
 
Social Networking (H.3.4 ... )
 
 
Time Series Analysis (G.3 ... )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Dynamic Programming": Date
Optimum decision trees--an optimal variable theorem and its related applications
Miyakawa M. Acta Informatica 22(5): 475-498, 1985. Type: Article
Mar 1 1987
An efficient algorithm for optimal pruning of decision trees
Almuallim H. Artificial Intelligence 83(2): 347-362, 1996. Type: Article
Apr 1 1997
Visual unrolling of network evolution and the analysis of dynamic discourse
Brandes U., Corman S. Information Visualization 2(1): 40-50, 2003. Type: Article
Dec 30 2003
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy