Multi-criteria partitioning and influence maximization in large graphs

PhD Thesis Proposal 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 aplayer 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:			Thursday, 24 May 2018

Time:                  	2:00pm - 4:00pm

Venue:                  Room 2610
                         lifts 31/32

Committee Members:	Prof. Dimitris Papadais (Supervisor)
  			Dr. Raymond Wong (Chairperson)
 			Prof. Frederick Lochovsky
 			Dr. Wilfred Ng


**** ALL are Welcome ****