Triangle packing for community detection : algorithms, visualizations and application to Twitter's network

Abstract : Relational data in our society are on a constant increasing, rising arduous challenges. In this thesis, we consider two aspects of relational data. First, we are interested in relational data with weighted relationship. As a concrete example, relationships among Twitter's users could be weighted with regard to their shared number of followers. The second aspect is related to the dynamism which is inherent to data nature. As an instance, in the previous example the number of common followers between two Twitter's users can change over time. In order to handle these complex and dynamic relational data, we use the modelling strength of graphs. Another facet considered in this thesis deals with community identification on weighted and dynamic graphs. For an analyst, the community detection might be helpful to grasp the semantic behind the graph structure. Our assumption relies on the idea to use a set of disjoint pairwise triangles as a basis to detect the community structure. To select these triangles, several algorithms are proposed (i.e., branch-and-bound, greedy search, heuristics and genetic algorithm). Thereafter, we propose a community detection algorithm, called Tribase. In the latter, the weights of communities are compared allowing dominant communities to gain in size. Tribase is compared with the well-known LFR benchmark. The results show that Tribase identifies efficiently the communities while a community structure exists. Additionally, to asset Tribase on real-world data, we consider social networks data, especially Twitter's data, of the ANR-Info-RSN project. In order to support the analyst in its knowledge acquisition, we elaborate a visual interactive approach. To this end, an interactive application, called NLCOMS is introduced. NLCOMS uses multiple synchronous views for visualizing community structure and the related information. Furthermore, we propose an algorithm for the identification of communities over time, called Dyci. The latter takes advantage from the previously detected communities. Several changes' scenarios are considered like, node/edge addition, node/edge removing and edge weight update. The main idea of the proposed algorithm is to track whether a part of the weighted graph becomes weak over time, in order to merge it with the "dominant" neighbour community. In order to assess the quality of the returned community structure, we conduct a comparison with a genetic algorithm on real-world data of the ARN-Info-RSN project. The conducted comparison shows that Dyci algorithm provides a good trade-off between efficiency and consumed time. Finally, the dynamic changes which occur to the underlying graph structure can be visualized with NLCOMS which combines physical an axial time to fulfil this need
Document type :
Theses
File URL :
http://docnum.univ-lorraine.fr/prive/DDOC_T_2016_0310_ABDELSADEK.pdf
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01752408
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 1:45:15 PM
Last modification on : Friday, March 30, 2018 - 1:28:55 AM

Identifiers

  • HAL Id : tel-01752408, version 1

Collections

Citation

Youcef Abdelsadek. Triangle packing for community detection : algorithms, visualizations and application to Twitter's network. Other [cs.OH]. Université de Lorraine, 2016. English. ⟨NNT : 2016LORR0310⟩. ⟨tel-01752408⟩

Share

Metrics

Record views

14