Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4955957 | Journal of Network and Computer Applications | 2017 | 23 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Wenyin Yang, Guojun Wang, Md Zakirul Alam Bhuiyan, Kim-Kwang Raymond Choo,