Efficient search algorithms for social networking scheduling applications

Subodh Kalia

Date of Award

6-30-2016

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Electrical Engineering and Computer Science

Advisor(s)

Chilukuri K. Mohan

Keywords

Evolutionary algorithms, Genetic algorithms, Optimization, Social network

Abstract

Social networks have recently emerged as the most important modality for inter-personal interactions, communication and information sharing. Examples include services from Facebook, Google+, Linkedin, Twitter, Tinder, OKCupid, etc., each of which has a specific purpose and caters to particular needs, but has some limitations. This thesis proposes a real-time social networking platform that facilitates finding others available to meet or participate on a shared activity during a mutually agreeable time period, accounting for several factors such as availability of users, choice of activities, geographical locations, and/or other preferences. The focus of this research is to design scalable, robust, and efficient algorithms to facilitate social interactions, searching for the most appropriate users from a large database. First, we focused on a single objective, viz., physical distance, and designed an efficient search algorithm that is applicable when user characteristics change constantly with time, and can be readily implemented on mobile devices. Such constraints imply that many traditional search algorithms are too computationally expensive. We proposed an evolutionary algorithm using a small population size and a new recombination operator (HMCC) for this task, accounting for the problem that traditional recombination operators may generate infeasible solutions. The new algorithm outperformed several existing algorithms, and scales well even when the number of users is very large. We then extended this algorithm to a multi-objective optimization context, considering other objectives such as user availability during a time period, and strength of relationship (in a social network) to the user who conducts the search. We developed a new multi-objective algorithm (MONA) for this task, combining aspects of multi-objective versions of evolutionary strategies and genetic algorithms. Experimental simulations with several large datasets showed that the new algorithm performed better than other multi-objective evolutionary algorithms, though not in all cases. Scalability of the algorithm was successfully demonstrated, with very large geographical areas and numbers of users; the number of function evaluations varied linearly with increasing input size. The proposed algorithm, framework and methodology are expected to be useful in many practical applications.

Access

SURFACE provides description only. Full text may be available to ProQuest subscribers. Please ask your Librarian for assistance.

This document is currently not available here.

Share

COinS