Tiago Simas

Tiago Simas, Rion Brattig Correia, Luis M. Rocha

Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges -- those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.

Tiago Simas, Luis M Rocha

To expand the toolbox available to network science, we study the isomorphism between distance and Fuzzy (proximity or strength) graphs. Distinct transitive closures in Fuzzy graphs lead to closures of their isomorphic distance graphs with widely different structural properties. For instance, the All Pairs Shortest Paths (APSP) problem, based on the Dijkstra algorithm, is equivalent to a metric closure, which is only one of the possible ways to calculate shortest paths. Understanding and mapping this isomorphism is necessary to analyse models of complex networks based on weighted graphs. Any conclusions derived from such models should take into account the distortions imposed on graph topology when converting proximity/strength into distance graphs, to subsequently compute path length and shortest path measures. We characterise the isomorphism using the max-min and Dombi disjunction/conjunction pairs. This allows us to: (1) study alternative distance closures, such as those based on diffusion, metric, and ultra-metric distances; (2) identify the operators closest to the metric closure of distance graphs (the APSP), but which are logically consistent; and (3) propose a simple method to compute alternative distance closures using existing algorithms for the APSP. In particular, we show that a specific diffusion distance is promising for community detection in complex networks, and is based on desirable axioms for logical inference or approximate reasoning on networks; it also provides a simple algebraic means to compute diffusion processes on networks. Based on these results, we argue that choosing different distance closures can lead to different conclusions about indirect associations on network data, as well as the structure of complex networks, and are thus important to consider.

Tiago Simas, Luis M. Rocha

Weighted graphs obtained from co-occurrence in user-item relations lead to non-metric topologies. We use this semi-metric behavior to issue recommendations, and discuss its relationship to transitive closure on fuzzy graphs. Finally, we test the performance of this method against other item- and user-based recommender systems on the Movielens benchmark. We show that including highly semi-metric edges in our recommendation algorithms leads to better recommendations.