A Hybrid Evolutionary Algorithm for Efficient Exploration of Online Social Networks

Authors

  • Zorica Stanimirović Faculty of Mathematics, University of Belgrade, Studentski trg 16/IV, 11 000 Belgrade
  • Stefan Mišković Faculty of Mathematics, University of Belgrade, Studentski trg 16/IV, 11 000 Belgrade

Keywords:

Hybrid optimization method, evolutionary algorithm, local search, social network, data flow

Abstract

Online social networks provide large amount of valuable data and may serve as research platforms for various social network analysis tools. In this study, we propose a mathematical model for efficient exploration of an online social network. The goal is to spend minimal amount of time searching for characteristics which define a sub-network of users sharing the same interest or having certain common property. We further develop an efficient hybrid method (HEA), based on the combination of an Evolutionary Algorithm (EA) with Local Search procedure (LS). The proposed mathematical model and hybrid method are benchmarked on real-size data set with up to 10 000 users in a considered social network. We provide optimal solutions obtained by CPLEX solver on problem instances with up to 100 users, while larger instances that were out of reach of the CPLEX were efficiently solved by the proposed hybrid method. Presented computational results show that the HEA approach quickly reaches all optimal solutions obtained by CPLEX solver and gives solutions for the largest considered instance in very short CPU time.

Downloads

Download data is not yet available.

Author Biography

Zorica Stanimirović, Faculty of Mathematics, University of Belgrade, Studentski trg 16/IV, 11 000 Belgrade

Assistant Professor, Dpt. for Numerical Mathematics and Optimization, Vice-Dean for Science & Research, Faculty of Mathematics, University of Belgrade, Serbia

Downloads

Published

2014-06-27

How to Cite

Stanimirović, Z., & Mišković, S. (2014). A Hybrid Evolutionary Algorithm for Efficient Exploration of Online Social Networks. Computing and Informatics, 33(2), 410–430. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/1048