Network data (also referred to as relational data, social network data, real graph data) has become ubiquitous, and understanding patterns in this data has become an important research problem. We investigate how interactions in social networks are formed and how these interactions facilitate diffusion, model these behaviors, and apply these findings to real-world problems. We examined graphs of size up to 16 million nodes, across many domains from academic citation networks, to campaign contributions and actor-movie networks. We also performed several case studies in online social networks such as blogs and message board communities. Our major contributions are the following: (a) We discover several surprising patterns in network topology and interactions, such as Popularity Decay power law (in-links to a blog post decay with a power law with -1:5 exponent) and the oscillating size of connected components; (b) We propose generators such as the Butterfly generator that reproduce both established and new properties found in real networks; (c) several case studies, including a proposed method of detecting misstatements in accounting data, where using network effects gave a significant boost in detection accuracy.

Graphs are a great tool for representing complex physical and social systems, where the interactions among many units, from tens of animal species in a food-web, to millions of users in a social network, give rise to emergent, complex system behaviours. In the field of network science this representation, which is usually called a complex network, can be complicated at will to better represent the real system under study. For instance, interactions may be directed or may differ in their strength or cost, leading to directed weighted networks, but they may also depend on time, like in temporal networks, or nodes (i.e. the units of the system) may interact in different ways, in which case edge-coloured multi-graphs and multi-layer networks represent better the system. Besides this rich repertoire of network structures, we cannot forgot that edges represent interactions and that this interactions are not static, but are, instead, purposely established to reach some function of the system, as for instance, routing people and goods through a transportation network or cognition, through the exchange of neuro-physiological signals in the brain. Building on the foundations of spectral graph theory, of non-linear dimensionality reduction and diffusion maps, and of the recently introduced diffusion distance [Phys. Rev. Lett. 118, 168301 (2017)] we use the simple yet powerful tool of continuous-time Markov chains on networks to model their process-driven geometry and characterise their functional shape. The main results are: (i) the generalisation of the diffusion geometry framework to different types of interconnected systems (from edge-coloured multigraphs to multi-layer networks) and of random walk dynamics [Phys. Rev. E 103, 042301 (2021)] and (ii) the introduction of new descriptors based on the diffusion geometry to quantify and describe the micro- (through the network depth [J. Complex Netw. 8, 4 (2020)]), meso- (functional rich-club) and macro-scale (using statistics of the pairwise distances between the network's nodes [Comm. Phys. 4, 125 (2021)]) of complex networks.

Les protéines sont des objets biologiques conçus pour résister aux perturbations et, àen même temps, s'adapter à des nouveaux environnements et des nouveaux besoins. Que sont lespropriétés structurelles des protéines permettant une telle plasticité? Pour taclercette question, nous modélisons d'abord la structure des protéines comme un réseau d'acides aminés et atomes en interaction. Compte tenu de la conformation structurelle 3Dd'une mutation obtenue In Silico, une approche réseaupermet la quantification de son changement structurel. En utilisant des grands ensemblesde mutations, nous avons conclu que le changement structurel est indépendant du type d'acide aminé remplacé ou du remplacement après mutation. En regardantà la composition des voisinages d'acides aminés, nous avons remarqué que lela localisation d'un type d'acide aminé dans la structure 3D est arbitraire:ce qui signifie que les contraintes d'interactions d'acides aminés dans une protéinemontre être indépendantes de la position de l'acide aminé en question. Menant à laobservation que la position de l'acide aminé dans la séquence est lapropriété unique modulant la plasticité structurelle.Le fait que les acides aminés peuvent se remplacer les uns les autres danstoutes les positions parce que la contrainte d'interaction ne dépend pas dutype d'acide aminé,est basé sur la personnalisation des voisins viamutations altérnatives compensatoires. Même s'il y a une grandetolérance pour les mutations basée sur la robustesse structurelle, les mutations peuvent avoir un impact surla plasticité structurelle en raison de la modification de la force des interactions êntre acides aminéset la distribution des atomes et des voisins entourant les résidus.La conséquence directe d'une telle variabilité de l'emballage atomique,est dû à une différence de vide (espace vide,pas d'atomes) sur la surface des résidus identifiés par certaines de mes données / résultats.Cela soulève la possibilité que la plasticité structurelle n'est pas seulementrégulée par les acides aminés et les contacts atomiques, mais aussi en sculptantdes vides locales dans la structure de la protéine pour permettre des mouvements atomiquesnécessaires pour la fonction de la protéine. Enfin, pour tester cette hypothèse, nous avonsmis en œuvre trois algorithmes pour mesurer l'espace vide autour desacides aminés pour regarder la relation entre cet espace vide et la plasticité structurelle. / Proteins are biological objects made to resist perturbations and, atthe same time, adapt to new environments and new needs. What are thestructural properties of proteins allowing such plasticity? To tacklethis question we first model protein structure as a network of aminoacids and atoms in interaction. Given the 3D structural conformationof a mutation obtained In Silico, a network approachallows the quantification of its structural change. Using large setsof mutations, we concluded that structural change is independent fromthe type of amino acid replaced, or replacing after mutation. Lookingat the composition of amino acid neighborhoods, we noticed that thelocation of a type of amino acid in the 3D structure is arbitrary:meaning that constraints of amino acid interactions in a proteinshow to be position independent. Leading to theobservation that the position of the amino acid in the sequence is thesingle property modulating structural plasticity.The fact that amino acids can replace each other atany position because the interaction constraint is not dependent on thetype of amino acid,is based on the customization of neighbors via alternative amino acidmutations or compensatory mutations. Even if there is a large mutationtolerance based on structural robustness, mutations can have an impact onthe structural plasticity because of the change in strength of pairwsie interactionsand the distribution of atoms and neihgbors surrounding residues.The direct consequence of such a variable atomic packingdistribution, is a difference of void (empty space,no atoms) on the surface of residues as identified by some of my data/results.This raises the possibility that structural plasticity is not onlyregulated by amino acid and atomic contacts but also by carving localvoids within the protein structure to allow atomic motionsrequired for the function of the protein. Finally, to test this hypothesis, we haveimplemented three algorithms to measure the empty space around aminoacids to look at the relation between this empty space and structural plasticity.