A Scalable Algorithm for Discovering Topologies in Social Networks

被引:2
作者
Yadav, Jyoti Rani [1 ]
Somayajulu, D. V. L. N. [1 ]
Krishna, P. Radha [2 ]
机构
[1] NIT Warangal, Dept Comp Sci & Engn, Hanamkonda, Telangana, India
[2] Infosys Ltd, Infosys Labs, Hyderabad, Andhra Pradesh, India
来源
2014 IEEE INTERNATIONAL CONFERENCE ON DATA MINING WORKSHOP (ICDMW) | 2014年
关键词
topology discovery; SNA; Giraph; clustering;
D O I
10.1109/ICDMW.2014.75
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Discovering topologies in a social network targets various business applications such as finding key influencers in a network, recommending music movies in virtual communities, finding active groups in network and promoting a new product. Since social networks are large in size, discovering topologies from such networks is challenging. In this paper, we present a scalable topology discovery approach using Giraph platform and perform (i) graph structural analysis and (ii) graph mining. For graph structural analysis, we consider various centrality measures. First, we find top-K centrality vertices for a specific topology (e.g. star, ring and mesh). Next, we find other vertices which are in the neighborhood of top centrality vertices and then create the cluster based on structural density. We compare our clustering approach with DBSCAN algorithm on the basis of modularity parameter. The results show that clusters generated through structural density parameter are better in quality than generated through neighborhood density parameter.
引用
收藏
页码:818 / 827
页数:10
相关论文
共 18 条
[1]  
[Anonymous], P 11 INT C SEC MAN S
[2]  
[Anonymous], P 5 ACM COMPUTE 12 C
[3]  
[Anonymous], 2004, Journal of Graph Algorithms and Applications, DOI 10.7155/jgaa.00081
[4]  
[Anonymous], SIAM INT C DAT MIN
[5]  
[Anonymous], SIAM INT C DAT MIN
[6]  
[Anonymous], LNCS
[7]   A faster algorithm for betweenness centrality [J].
Brandes, U .
JOURNAL OF MATHEMATICAL SOCIOLOGY, 2001, 25 (02) :163-177
[8]  
Ester M., 1996, KDD-96 Proceedings. Second International Conference on Knowledge Discovery and Data Mining, P226
[9]   DENGRAPH: A density-based community detection algorithm [J].
Falkowski, Tanja ;
Barth, Anja ;
Spiliopoulou, Myra .
PROCEEDINGS OF THE IEEE/WIC/ACM INTERNATIONAL CONFERENCE ON WEB INTELLIGENCE: WI 2007, 2007, :112-115
[10]   PROBABILISTIC COUNTING ALGORITHMS FOR DATABASE APPLICATIONS [J].
FLAJOLET, P ;
MARTIN, GN .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 31 (02) :182-209