کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4955957 | 1444374 | 2017 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hypergraph partitioning for social networks based on information entropy modularity
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A social network is a typical scale-free network with power-law degree distribution characteristics. It demonstrates several natural imbalanced clusters when it is abstracted as a graph, and expands quickly under its generative mechanism. Hypergraph is superior for modeling multi-user operations in social networks, and partitioning the hypergraph modeled social networks could ease the scaling problems. However, today's popular hypergraph partitioning tools are not sufficiently scalable; thus, unable to achieve high partitioning quality for naturally imbalanced datasets. Recently proposed hypergraph partitioner, hyperpart, replaces the balance constraint with an entropy constraint to achieve high-fidelity partitioning solutions, but it is not tailored for scale-free networks, like social networks. In order to achieve scalable and high quality partitioning results for hypergraph modeled social networks, we propose a partitioning method, EQHyperpart, which utilizes information-Entropy-based modularity Q value (EQ) to direct the hypergraph partitioning process. This EQ considers power-law degree distribution while describing the “natural” structure of scale-free networks. We then apply simulated annealing and introduce a new definition of hyperedge cut, micro cut, to avoid the local minima in convergence of partitioning, developing EQHyperpart into two specific partitioners, namely: EQHyperpart-SA and EQHyperpart-MC. Finally, we evaluate the utility of our proposed method using classical social network datasets, including Facebook dataset. Findings show that EQHyperpart partitioners are more scalable than competing approaches, achieving a tradeoff between modularity retaining and cut size minimizing under balance constraints, and an auto-tradeoff without balance constraints for hypergraph modeled social networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Network and Computer Applications - Volume 86, 15 May 2017, Pages 59-71
Journal: Journal of Network and Computer Applications - Volume 86, 15 May 2017, Pages 59-71
نویسندگان
Wenyin Yang, Guojun Wang, Md Zakirul Alam Bhuiyan, Kim-Kwang Raymond Choo,