École Nationale Supérieure de
Techniques Avancées

Abstract

Community structures are quite common in real networks including social networks and biological networks. Being able to identify these sub-structure properties can provide insight into how the topology functions and be useful in improving algorithms on graphs. During the internship we focus on two topics: influence maximization and image segmentation. The approaches we use are both related to community structure of respective network. Based on the influence locality feature we propose an efficient algorithm, MATM, for influence computation of a set of nodes under two basic diffusion models. The new computation method can be applied on a classical combinatorial problem: influence maximization. According to our experiments on large-scale social networks, the improved algorithm is at least 1000 times faster than the original greedy algorithm. Identification of community structure of image network provides us a new approach for image segmentation. We present a new perspective of image segmentation, by applying three of the most efficient community detection algorithms. We show that modularity-based algorithms achieve better results than the others and modularity is also invariant to non-structural change on image.