| Přispěvatelé: |
UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique, UCL - Ecole Polytechnique de Louvain, Van Dooren, Paul, Absil, Pierre-Antoine, Jungers, Raphael, Devleeschouwer, Christophe, Lambiotte, Renaud, Barahona, Mauricio |
| Popis: |
Many real networks encompass a community structure which means that nodes are organized in densely connected groups with, at the same time, relatively few links between the groups. We propose a new algorithm to uncover those community structures in very large networks based on an efficient representation of the most important interactions in the graph. This framework allows our algorithm to converge much faster than its competitors while extracting results of similar accuracy. Moreover, our method can efficiently use multiple processors synchronously to further decrease the computational time or to analyze larger networks. Yet, a partition in communities is not always representative of the actual distribution of the nodes. We consider a generalization of the problem of community detection, termed role extraction, which does not use any prior assumption on the links distribution in the graph. To extract a role structure, we describe a similarity measure based on the number of common neighbors between each pair of nodes and we propose an iterative scheme to compute a low-rank approximation of the similarity matrix. Our low-rank similarity measure has interesting properties that reveal characteristics of the role structure in benchmark and real graphs. (FSA - Sciences de l) -- UCL, 2014 |
