Role extraction in networks

Cason, Thomas
(2012)

Files

Thesis3.pdf
  • Open Access
  • Adobe PDF
  • 1.82 MB
Download

Details

Authors
  • Cason, ThomasUCLouvain
    author
Supervisors
Absil, Pierre-Antoine
 ;
Van Dooren, Paul
Abstract
(en) Graphs allow to represent real problems in an abstract fashion which, though easily stated, raises non trivial mathematical problems. In the past few years, several large networks have become omnipresent in everyday life, which made their analysis a major concern. The notion of regularity for equivalence relations is one of the many analysis tools used in graph theory to reduce large graphs into smaller comprehensible structures. It consists in partitioning the nodes of a graph in blocks of nodes that play the same role in the graph. Unfortunately, this notion is very sensitive to small perturbations of the graph under consideration. This thesis focuses on two analysis tools that remedy this sensitivity, node-to-node self-similarity measures, and Blockmodeling, which regularly require one to solve non-trivial trace maximization problems. Node-to-node similarity measures assign real values to each pair of nodes that tells how the first node is similar to the second one based on particular criteria. In this thesis, we introduce the notion of weak and strong compatibility which links self-similarity measures to equivalence relations. We analyze several existing similarity measures, and propose alternative definitions which improve the earlier. Blockmodeling consists in finding equivalence relations in a graph that would be regular if few modifications were made to the original graph. In this thesis, we analyze existing Blockmodel quality measures, and propose alternative definitions which improve the earlier. We propose an algorithm to find relevant Blockmodels and test it on the Baydry network, a food web observed in the Florida bay. Node-to-Node Similarity Measures and Blockmodeling regularly require one to solve non-trivial trace maximization problems. In this thesis, we finally consider several trace maximization problems associated to a particular node-to-node similarity measure, and consider restrictions of the feasible set to sets of low-rank matrices.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Cason, T. (2012). Role extraction in networks. https://hdl.handle.net/2078.5/160341