MULTI-CRITERIA PARTITIONING AND INFLUENCE MAXIMIZATION IN LARGE GRAPHS

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "MULTI-CRITERIA PARTITIONING AND INFLUENCE MAXIMIZATION IN LARGE GRAPHS"

By

Mr. Eleftherios NTAFLOS


Abstract

Large graphs are prominent in several domains including data management, 
computer vision and language modeling. In this thesis, we target common 
scenarios related to Geo-Social networks. In particular, we focus on two 
fundamental problems: i) multicriteria partitioning in the presence of 
constraints and ii) influence maximization for the case of several competitors. 
Initially, we introduce a robust agent-based framework that tackles the 
Constrained Graph Partitioning (CGP) problem. CGP can be useful for 
recommendations of social events, or delivery of targeted advertising material 
to certain users. It assigns users of a social network to a set of classes with 
bounded capacities so that the similarity and the social costs are minimized. 
The similarity cost is proportional to the dis-similarity between a user and 
his class, whereas the social cost is measured in terms of friends that are 
assigned to different classes. We investigate two solutions for CGP. The first 
utilizes a game-theoretic framework, where each user constitutes a player that 
wishes to minimize his own social and similarity cost. The second employs local 
search, and aims at minimizing the global cost. We show that the two approaches 
can be unified under a common agent-based framework that allows for two types 
of deviations. In a unilateral deviation an agent switches to a new class, 
whereas in a bilateral deviation a pair of agents exchange their classes. We 
develop a number of optimization techniques to improve result quality and 
facilitate efficiency. Our experimental evaluation on real datasets 
demonstrates that the proposed methods always outperform the state-of-the art 
in terms of solution quality, while they are up to an order of magnitude 
faster.

For the second case, we focus on competitive influence maximization, where 
multiple competitors wish to influence the users of a social network; e.g., 
advertisers marketing similar products. In addition, we consider that users 
have weights according to their importance (e.g., users whose profile or 
demographic characteristics match the advertised product have high weights). 
Therefore, we introduce the novel Competitive Weighted Influence Maximization 
CWim problem. We first present an Awareness-to-Influence (AtI) model that 
distinguishes the concepts of awareness and influence. AtI is motivated by the 
fact that usually users do not blindly follow the first influence; instead they 
collect information, reproduce it and finally decide. We then prove that AtI 
also exhibits monotonicity and submodularity, which facilitate tight quality 
guarantees. Next we develop algorithms based on a game theoretic framework, 
considering that each competitor is a player that chooses a strategy (i.e., 
seed set) in order to maximize his own benefit. Our experimental findings 
suggest that the proposed method outperform considerably some benchmarks and 
scale very well to large social networks.


Date:			Friday, 7 December 2018

Time:			2:00pm - 4:00pm

Venue:			Room 5508
 			Lifts 25/26

Chairman:		Prof. Jeffrey Chasnov (MATH)

Committee Members:	Prof. Dimitrios Papadias (Supervisor)
 			Prof. Frederick Lochovsky
 			Prof. Raymond Wong
 			Prof. Ajay Joneja (IDEA)
 			Prof. Matthias Renz (CAU Kiel)


**** ALL are Welcome ****