Shi, Bowen (2016) Community Structure and Its Applications in Complex Network PFE - Project Graduation, ENSTA.



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.

Item Type:Thesis (PFE - Project Graduation)
Uncontrolled Keywords:   Community   Detection,   Influence   Maximization,   Image   Segmentation 
Subjects:Information and Communication Sciences and Technologies
ID Code:6764
Deposited By:Bowen SHI
Deposited On:07 sept. 2016 16:38
Dernière modification:07 sept. 2016 16:38

Repository Staff Only: item control page