With the recent growth of social media platforms and the human desire to interact with the digital world a lot of human-human and human-device interaction data is getting generated every second. With the boom of the Internet of Things (IoT) devices, a lot of device-device interactions are also now on the rise. All these interactions are nothing but a representation of how the underlying network is connecting different entities over time. These interactions when modeled as an interaction network presents a lot of unique opportunities to uncover interesting patterns and to understand the dynamics of the network. Understanding the dynamics of the network is very important because it encapsulates the way we communicate, socialize, consume information and get influenced. To this end, in this PhD thesis, we focus on analyzing an interaction network to understand how the underlying network is being used. We define interaction network as a sequence of time-stamped interactions E over edges of a static graph G=(V, E). Interaction networks can be used to model many real-world networks for example, in a social network or a communication network, each interaction over an edge represents an interaction between two users, e.g. emailing, making a call, re-tweeting, or in case of the financial network an interaction between two accounts to represent a transaction.We analyze interaction network under two settings. In the first setting, we study interaction network under a sliding window model. We assume a node could pass information to other nodes if they are connected to them using edges present in a time window. In this model, we study how the importance or centrality of a node evolves over time. In the second setting, we put additional constraints on how information flows between nodes. We assume a node could pass information to other nodes only if there is a temporal path between them. To restrict the length of the temporal paths we consider a time window in this approach as well. We apply this model to solve the time-constrained influence maximization problem. By analyzing the interaction network data under our model we find the top-k most influential nodes. We test our model both on human-human interaction using social network data as well as on location-location interaction using location-based social network(LBSNs) data. In the same setting, we also mine temporal cyclic paths to understand the communication patterns in a network. Temporal cycles have many applications and appear naturally in communication networks where one person posts a message and after a while reacts to a thread of reactions from peers on the post. In financial networks, on the other hand, the presence of a temporal cycle could be indicative of certain types of fraud. We provide efficient algorithms for all our analysis and test their efficiency and effectiveness on real-world data.Finally, given that many of the algorithms we study have huge computational demands, we also studied distributed graph processing algorithms. An important aspect of these algorithms is to correctly partition the graph data between different machines. A lot of research has been done on efficient graph partitioning strategies but there is no one good partitioning strategy for all kind of graphs and algorithms. Choosing the best partitioning strategy is nontrivial and is mostly a trial and error exercise. To address this problem we provide a cost model based approach to give a better understanding of how a given partitioning strategy is performing for a given graph and algorithm. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Serverless Function as a Service (FaaS) platforms have been an emerging trend nowadays with the continuous improvement of the cloud-native ecosystem. Graph streaming analytics is a widely-known research area that demands well-designed computation paradigms and complex optimization of storage and queries. Using serverless platforms to process graph streaming analytics would be a prospective field. For one thing, serverless platforms normally use a Function as the first-class citizen, and users can smoothly use or expand the Functions only caring about the application layer, to get the results without knowing the beneath architectures or environment. For another, distributed large-scale graph problems normally demand the message-passing actor model and serverless platforms could use one Function instance for one vertex with its own context, and each of the Functions could evolve its state by passing messages to each other. This way of processing is native to distributed stateful applications and can smoothly support graph streaming analytics. A temporal graph is a graph that evolves with time. With timestamps on edges, users can retrieve historical graph states and even retrieve graph states in any arbitrary event time windows for further analytics. Handling temporal graph analytics problems on serverless platforms is the focus of this thesis. Flink Stateful Functions, a newly-built API under the umbrella of Apache Flink, simplifies the building of distributed stateful applications with runtime for serverless architectures, with the full support of stateful entities modeling with location transparency, concurrency, scaling, and resiliency. Flink Stateful Functions is a powerful tool for temporal graph streaming analytics on a serverless platform. In this thesis project, a temporal graph processing library is built based on the Flink Stateful Functions. It supports efficient storage and query specifically on temporal graph analytics problems. / Serverlösa FaaS-plattformar har varit en framväxande trend nuförtiden med den kontinuerliga förbättringen av det molnbaserade ekosystemet. Grafströmningsanalys är ett allmänt känt forskningsområde som kräver väldesignade beräkningsparadigm och komplex optimering av lagring och frågor. Att använda serverlösa plattformar för att bearbeta grafströmningsanalyser skulle vara ett potentiellt område. För det första använder serverlösa plattformar normalt en funktion som den förstklassiga medborgaren, och användare kan smidigt använda eller utöka funktionerna som bara bryr sig om applikationslagret, för att få resultat utan att känna till underarkitekturerna eller miljön. För ett annat kräver distribuerade storskaliga grafproblem normalt den meddelandeöverförande aktörsmodellen och serverlösa plattformar kan använda en funktionsinstans för en vertex med sitt eget sammanhang, och var och en av funktionerna kan utveckla sitt tillstånd genom att skicka meddelanden till varandra. Det här sättet att bearbeta är inbyggt i distribuerade statistiska applikationer och kan smidigt stödja grafströmningsanalys. En tidsgraf är en graf som utvecklas med tiden. Med tidsstämplar på kanterna kan användare hämta historiskt graftillstånd och till och med hämta graftillstånd i alla godtyckliga händelsetidsfönster för ytterligare analys. Att hantera tidsmässiga grafanalysproblem på serverlösa plattformar är fokus för denna avhandling. Flink Stateful Functions, ett nybyggt API under Apache Flinks paraply, förenklar byggandet av distribuerade stateful-applikationer med runtime för serverlösa arkitekturer, med fullt stöd av stateful entitetsmodellering med platstransparens, samtidighet, skalning och resiliens. Flink Stateful Functions är ett kraftfullt verktyg för temporal grafströmningsanalys på en serverlös plattform. I detta examensarbete byggs ett bibliotek för temporal grafbehandling baserat på Flink Stateful Functions. Den stöder effektiv lagring och frågesökning specifikt på temporal grafdata för att lösa storskaliga grafproblem.

We address the problem of all-pairs shortest time communication of messages in futuregeneration 6G networks by modeling the highly dynamic characteristics of the network using a temporal graph. Based on this model, an elegant technique is proposed to devise an algorithm for finding the all-pairs shortest time paths in the temporal graph that can be used for all-pairs internodes communication of messages in the network. The proposed algorithm basically involves computations similar to only two matrix multiplication steps, once in the forward direction and then in the backward direction.

Στη διπλωματική εργασία προς παρουσίαση, πραγματευόμαστε ένα νέο είδος γραφημάτων, τα χρονικά γραφήματα, και διάφορες παραλλαγές τους. Ένα χρονικό γράφημα είναι μια διατεταγμενη τριάδα G={V,E,L}, όπου V ένα μη κενό πεπερασμένο σύνολο που καλείται σύνολο κορυφών, E ένα σύνολο m στοιχείων, καθένα από τα οποία είναι δισύνολο στοιχείων του V (καλείται σύνολο ακμών), και L= {L_e, για κάθε e στοιχείο του E} = {L_e_1, L_e_2, ..., L_e_m}, όπου L_e_i, i = 1,..., m, σύνολο θετικών ακεραίων τιμών που αντιστοιχίζονται στην ακμή e_i του συνόλου E (καλείται ανάθεση χρονικών ετικετών ή απλώς ανάθεση). Οι τιμές που αντιστοιχίζονται σε κάθε ακμή του γραφήματος καλούνται χρονικές ετικέτες της ακμής και δηλώνουν τις χρονικές στιγμές, κατά τις οποίες έχουμε τη δυνατότητα να τη διασχίσουμε (από το ένα της άκρο προς το άλλο). Για να αντιληφθεί κανείς το ενδιαφέρον των χρονικών γραφημάτων, μπορεί να σκεφτεί τη δυνατότητα εφαρμογής τους στην καθημερινότητα. Για παράδειγμα, οι χρονικές ετικέτες που ανατίθενται σε μία ακμή ενός κατευθυνόμενου χρονικού γραφήματος μπορούν να παραλληλιστούν με τις ώρες, στις οποίες γίνονται αναχωρήσεις αεροπλάνων από μία πόλη προς μια άλλη. Έτσι, η μελέτη των χρονικών γραφημάτων θα μπορούσε να συμβάλει στην οργάνωση των πτήσεων ενός αεροδρομίου. Ένα χρονικό μονοπάτι (ή «ταξίδι») σε ένα χρονικό γράφημα είναι ένα μονοπάτι, στις ακμές του οποίου μπορούμε να βρούμε αυστηρά αύξουσα σειρά χρονικών ετικετών. Στην εργασία, μεταξύ άλλων, γίνεται μελέτη της συνδετικότητας στα χρονικά γραφήματα, καθώς και κατασκευή και μελέτη αλγορίθμων εύρεσης χρονικών μονοπατιών («ταξιδίων») που φθάνουν το δυνατόν συντομότερα στον προορισμό τους (τελική κορυφή μονοπατιού). Επιπλέον, μελετώνται στατιστικά τα Χρονικά Γραφήματα, με επικέντρωση στο αναμενόμενο πλήθος χρονικών μονοπατιών σε ένα γράφημα, καθώς και στη Χρονική Διάμετρο ενός γραφήματος, όπως αυτή ορίζεται στην εργασία. / In the thesis, we are dealing with a new type of graphs,called Temporal Graphs, and several variants. A temporal graph is an ordered triplet G={V,E,L}, where V stands for a nonempty finite set (called set of vertices), E stands for a set of m elements, each of which are 2-element subsets of V (called set of edges), and L= {L_e, for all e in E} = {L_e_1, L_e_2, ..., L_e_m}, where L_e_i, i = 1, ..., m, is a set of positive integers mapped to edge e_i in E (called assignment of time labels or simply assignment). The values assigned to each edge of the graph are called time labels of the edge and indicate the times at which we can cross it (from one end to the other). In order to understand the interest of temporal graphs, one may think their applicability to everyday life. For example, the time labels assigned to an edge of a directed temporal graph can be paralleled to the flight departure times from one city to another. Therefore, the study of temporal graphs could contribute to the organization of flights at an airport. A temporal path (or «journey») in a temporal graph is a path, on the edges of which we can find strictly ascending time labels. In the thesis, among others, we study the connectivity of temporal graphs and we construct and study several algorithms that find temporal paths which arrive the soonest possible at their destination (final vertice of the path). Furthermore, we examine temporal graphs statistically, focusing on the expected number of temporal paths in a graph as well as in the Temporal Diameter of a graph, also defined in the thesis.

Les flux d’information suivent aujourd’hui des chemins complexes: la propagation des informations, impliquant éditeurs on-line, chaînes d’information en continu et réseaux sociaux, emprunte alors des chemins croisés, susceptibles d’agir sur le contenu et sa perception. Ce projet de thèse étudie l’adaptation des mesures de graphes classiques aux graphes multiplexes en relation avec le domaine étudié, propose de construire des visualisations à partir de plusieurs représentations graphiques des réseaux, et de les combiner (visualisations multi-vues synchronisées, représentations hybrides, etc.). L’accent est mis sur les modes d’interaction permettant de prendre en compte l’aspect multiplexe (multicouche) des réseaux. Ces représentations et manipulations interactives s’appuient aussi sur le calcul d’indicateurs propres aux réseaux multiplexes. Ce travail est basé sur deux jeux de données principaux: l’un est une archive de 12 ans de l’émission japonaise publique quotidienne NHK News 7, de 2001 à 2013. L’autre recense les participants aux émissions de télévision/radio françaises entre 2010 et 2015. Deux systèmes de visualisation s’appuyant sur une interface Web ont été développés pour analyser des réseaux multiplexes, que nous appelons «Visual Cloud» et «Laputa». Dans le Visual Cloud, nous définissons formellement une notion de similitude entre les concepts et les groupes de concepts que nous nommons possibilité de co-occurrence (CP). Conformément à cette définition, nous proposons un algorithme de classification hiérarchique. Nous regroupons les couches dans le réseau multiplexe de documents, et intégrons cette hiérarchie dans un nuage de mots interactif. Nous améliorons les algorithmes traditionnels de disposition de mise en forme de nuages de mots de sorte à préserver les contraintes sur la hiérarchie de concepts. Le système Laputa est destiné à l’analyse complexe de réseaux temporels denses et multidimensionnels. Pour ce faire, il associe un graphe à une segmentation. La segmentation par communauté, par attribut, ou encore par tranche temporelle, forme des vues de ce graphe. Afin d’associer ces vues avec le tout global, nous utilisons des diagrammes de Sankey pour révéler l’évolution des communautés (diagrammes que nous avons augmentés avec un zoom sémantique). Cette thèse nous permet ainsi de parcourir trois aspects (3V) des plus intéressants de la donnée et du BigData appliqués aux archives multimédia: Le Volume de nos données dans l’immensité des archives, nous atteignons des ordres de grandeurs qui ne sont pas praticables pour la visualisation et l’exploitation des liens. La Vélocité à cause de la nature temporelle de nos données (par définition). La Variété qui est un corollaire de la richesse des données multimédia et de tout ce que l’on peut souhaiter vouloir y investiguer. Ce que l’on peut retenir de cette thèse c’est que la traduction de ces trois défis a pris dans tous les cas une réponse sous la forme d’une analyse de réseaux multiplexes. Nous retrouvons toujours ces structures au coeur de notre travail, que ce soit de manière plus discrète dans les critères pour filtrer les arêtes par l’algorithme Simmelian backbone, que ce soit par la superposition de tranches temporelles, ou bien que ce soit beaucoup plus directement dans la combinaison d’indices sémantiques visuels et textuels pour laquelle nous extrayons les hiérarchies permettant notre visualisation. / Nowadays, information follows complex paths: information propagation involving on-line editors, 24-hour news providers and social medias following entangled paths acting on information content and perception. This thesis studies the adaptation of classical graph measurements to multiplex graphs, to build visualizations from several graphical representations of the networks, and to combine them (synchronized multi-view visualizations, hybrid representations, etc.). Emphasis is placed on the modes of interaction allowing to take in hand the multiplex nature (multilayer) of the networks. These representations and interactive manipulations are also based on the calculation of indicators specific to multiplex networks. The work is based on two main datasets: one is a 12-year archive of the Japanese public daily broadcast NHK News 7, from 2001 to 2013. Another lists the participants in the French TV/radio shows between 2010 and 2015. Two visualization systems based on a Web interface have been developed for multiplex network analysis, which we call "Visual Cloud" and "Laputa". In the Visual Cloud, we formally define a notion of similarity between concepts and groups of concepts that we call co-occurrence possibility (CP). According to this definition, we propose a hierarchical classification algorithm. We aggregate the layers in a multiplex network of documents, and integrate that hierarchy into an interactive word cloud. Here we improve the traditional word cloud layout algorithms so as to preserve the constraints on the concept hierarchy. The Laputa system is intended for the complex analysis of dense and multidimensional temporal networks. To do this, it associates a graph with a segmentation. The segmentation by communities, by attributes, or by time slices, forms views of this graph. In order to associate these views with the global whole, we use Sankey diagrams to reveal the evolution of the communities (diagrams that we have increased with a semantic zoom). This thesis allows us to browse three aspects of the most interesting aspects of the data miming and BigData applied to multimedia archives: The Volume since our archives are immense and reach orders of magnitude that are usually not practicable for the visualization; Velocity, because of the temporal nature of our data (by definition). The Variety that is a corollary of the richness of multimedia data and of all that one may wish to want to investigate. What we can retain from this thesis is that we met each of these three challenges by taking an answer in the form of a multiplex network analysis. These structures are always at the heart of our work, whether in the criteria for filtering edges using the Simmelian backbone algorithm, or in the superposition of time slices in the complex networks, or much more directly in the combinations of visual and textual semantic indices for which we extract hierarchies allowing our visualization.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-30T17:17:25Z No. of bitstreams: 1 marinaivanovpereirajosue.pdf: 1327137 bytes, checksum: 2b404732ed5a5dd800a9c7adb3194f8f (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-06-01T11:35:39Z (GMT) No. of bitstreams: 1 marinaivanovpereirajosue.pdf: 1327137 bytes, checksum: 2b404732ed5a5dd800a9c7adb3194f8f (MD5) / Made available in DSpace on 2017-06-01T11:35:39Z (GMT). No. of bitstreams: 1 marinaivanovpereirajosue.pdf: 1327137 bytes, checksum: 2b404732ed5a5dd800a9c7adb3194f8f (MD5) Previous issue date: 2016-06-30 / Atualmente o conteúdo hipermídia pode ser entregue utilizando diferentes tecnologias de rede, como a TV Digital terrestre por satélite, IPTV e Web. Por isso, as máquinas de apresentação hipermídia devem levar em conta as especificidades dessas redes suportadas, de modo a prover os níveis de QoS/QoE esperados pelo usuário do conteúdo. Máquinas de apresentação avançadas podem empregar também a análise de conteúdo para auxiliar na tarefa de manutenção dos níveis de QoE. De modo especial, quando o conteúdo hipermídia inclui dados enviados por pull, as máquinas de apresentação podem criar um Plano de Pré- Busca baseado no comportamento da apresentação extraído da especificação do conteúdo. Entretanto, quando o conteúdo hipermídia inclui dados enviados por push, a análise do conteúdo deve ser transferida para o lado do servidor e se basear na construção de um Plano de Transmissão de Conteúdo. O Plano de Transmissão de Conteúdo é uma estrutura de dados que prevê os instantes em que objetos de mídia devem ser transmitidos, e por quanto tempo, para otimizar o uso de recursos fim-a-fim como largura de banda e espaço de armazenamento nos receptores. Este trabalho propõe um framework para gerenciamento da entrega de conteúdo hipermídia em modo push. O framework é genérico o suficiente para ser adaptável a diferentes cenários de entrega de conteúdo que podem empregar diferentes protocolos e técnicas de gerenciamento. Alguns cenários de instanciação do framework e seus respectivos resultados são discutidos nesta dissertação. / Nowadays hypermedia content may be delivered using different networking technolo- gies, such as terrestrial broadcasting, satellite, IPTV and the Web. Therefore hypermedia presentation engines must be designed taking into consideration the specificities of their supported networks, in order to provide the expected QoS/QoE levels. Advanced pre sentation engines should also employ hypermedia content analysis to help on the task of maintaining QoE levels. Specifically, when the hypermedia content includes pulled data, presentation engines may create a Content Prefetching Plan based on the presentation behavior learned from the specification of that content. However, when the hypermedia content includes pushed data, this content analysis should be transferred to the server side and be taken as a basis for building the so-called Content Transmission Plan. The Content Transmission Plan is a data structure that predicts the time when media objects should start to be transmitted and for how long, in order to optimize end-to-end resource usage such as communication bandwidth and storage space in receivers. This work pro poses a framework for managing the push-mode delivery of hypermedia content. The framework is generic enough to be instantiated over different content delivery scenarios that may employ different protocols and management techniques. Several instantiation scenarios and their respective results are also discussed in this dissertation.

Approximately 20% of the body’s energy consumption is ongoingly consumed by the brain, where the main part is due to the neural activity, which is only increased slightly when doing a demanding task. This ongoingly neural activity are studied with the so called resting-state fMRI, which mean that the neural activity in the brain is measured for participants with no specific task. These studies have been useful to understand the neural function and how the neural networks are constructed and cooperate. This have also been helpful in several clinical research, for example have differences been identified between bipolar disorder and major depressive disorder. Recent research has focused on temporal properties of the ongoing activity and it is well known that neural activity occurs in bursts. In this study, resting-state fMRI data and temporal graph theory is used to develop a point based method (PBM) to quantify these bursts at a nodal level. By doing this, the bursty pattern can be further investigated and the nodes showing the most bursty pattern (i.e hubs) can be identified. The method developed shows a robustness regarding several different aspects. In the method is two different variance threshold algorithms suggested. One local variance threshold (LVT) based on the individual variance of the edge time-series and one global variance threshold (GVT) based on the variance of all edges time-series, where the GVT shows the highest robustness. However, the choice of threshold needs to be adapted for the aims of the current study. Finally, this method ends up in a new measure to quantify this bursty pattern named bursty centrality. The derived temporal graph theoretical measure was correlated with traditional static graph properties used in resting state and showed a low but significant correlation. By applying this method on resting-state fMRI data for 32 young adults was it possible to identify regions of the brain that showed the most dynamic properties, these regions differed between the two thresholding algorithms

The increasing complexity of telecom networks, induced by the recent development of 5G, is a challenge for detecting faults in the telecom network. In addition to the structural complexity of telecommunication systems, data accessibility has become an issue both in terms of privacy and access cost. We propose a method relying on bi-level Federated Graph Neural Networks to identify anomalies in the telecom network while ensuring reduced communication costs as well as data privacy. Our method considers telecom data as a bi-level graph, where the highest level graph represents the interaction between sites, and each site is further expanded to its software (SW) performance behaviour graph. We developed and compared 4G/5G SW Fault Detection models under 3 settings: (1) Centralized Temporal Graph Neural Networks model: we propose a model to detect anomalies in 4G/5G telecom data. (2) Federated Temporal Graph Neural Networks model: we propose Federated Learning (FL) as a mechanism for privacy-aware training of models for fault detection. (3) Personalized Federated Temporal Graph Neural Networks model: we propose a novel aggregation technique, referred to as FedGraph, leveraging both a graph and the similarities between sites for aggregating the models and proposing models more personalized to each site’s behaviour. We compare the benefits of Federated Learning (FL) models (2) and (3) with centralized training (1) in terms of SW performance data modelling, anomaly detection, and communication cost. The evaluation includes both a scenario with normal functioning sites and a scenario where only a subset of sites exhibit faulty behaviour. The combination of SW execution graphs with GNNs has shown improved modelling performance and minor gains in centralized settings (1). In a normal network context, FL models (2) and (3) perform comparably to centralized training (CL), with slight improvements observed when using the personalized strategy (3). However, in abnormal network scenarios, Federated Learning falls short of achieving comparable detection performance to centralized training. This is due to the unintended learning of abnormal site behaviour, particularly when employing the personalized model (3). These findings highlight the importance of carefully assessing and selecting suitable FL strategies for anomaly detection and model training on telecom network data. / Den ökande komplexiteten i telenäten, som är en följd av den senaste utvecklingen av 5G, är en utmaning när det gäller att upptäcka fel i telenäten. Förutom den strukturella komplexiteten i telekommunikationssystem har datatillgänglighet blivit ett problem både när det gäller integritet och åtkomstkostnader. Vi föreslår en metod som bygger på Federated Graph Neural Networks på två nivåer för att identifiera avvikelser i telenätet och samtidigt säkerställa minskade kommunikationskostnader samt dataintegritet. Vår metod betraktar telekomdata som en graf på två nivåer, där grafen på den högsta nivån representerar interaktionen mellan webbplatser, och varje webbplats utvidgas ytterligare till sin graf för programvarans (SW) prestandabeteende. Vi utvecklade och jämförde 4G/5G SW-feldetekteringsmodeller under 3 inställningar: (1) Central Temporal Graph Neural Networks-modell: vi föreslår en modell för att upptäcka avvikelser i 4G/5G-telekomdata. (2) Federated Temporal Graph Neural Networks-modell: vi föreslår Federated Learning (FL) som en mekanism för integritetsmedveten utbildning av modeller för feldetektering. I motsats till centraliserad inlärning aggregeras lokalt tränade modeller på serversidan och skickas tillbaka till klienterna utan att data läcker ut mellan klienterna och servern, vilket säkerställer integritetsskyddande samarbetsutbildning. (3) Personaliserad Federated Temporal Graph Neural Networks-modell: vi föreslår en ny aggregeringsteknik, kallad FedGraph, som utnyttjar både en graf och likheterna mellan webbplatser för att aggregera modellerna. Vi jämför fördelarna med modellerna Federated Learning (FL) (2) och (3) med centraliserad utbildning (1) när det gäller datamodellering av SW-prestanda, anomalidetektering och kommunikationskostnader. Utvärderingen omfattar både ett scenario med normalt fungerande anläggningar och ett scenario där endast en delmängd av anläggningarna uppvisar felaktigt beteende. Kombinationen av SW-exekveringsgrafer med GNN har visat förbättrad modelleringsprestanda och mindre vinster i centraliserade inställningar (1). I en normal nätverkskontext presterar FL-modellerna (2) och (3) jämförbart med centraliserad träning (CL), med små förbättringar observerade när den personliga strategin används (3). I onormala nätverksscenarier kan Federated Learning dock inte uppnå jämförbar detekteringsprestanda med centraliserad träning. Detta beror på oavsiktlig inlärning av onormalt beteende på webbplatsen, särskilt när man använder den personliga modellen (3). Dessa resultat belyser vikten av att noggrant bedöma och välja lämpliga FL-strategier för anomalidetektering och modellträning på telekomnätdata.

<p>The most important networks from different domains—such as Computing, Organization, Economic, Social, Academic, and Biology—are networks that change over time. For example, in an organization there are email and collaboration networks (e.g., different people or teams working on a document). Apart from the connectivity of the networks changing over time, they can contain attributes such as the topic of an email or message, contents of a document, or the interests of a person in an academic citation or a social network. Analyzing these dynamic networks can be critical in decision-making processes. For instance, in an organization, getting insight into how people from different teams collaborate, provides important information that can be used to optimize workflows.</p> <p><br></p> <p>Network generative models provide a way to study and analyze networks. For example, benchmarking model performance and generalization in tasks like node classification, can be done by evaluating models on synthetic networks generated with varying structure and attribute correlation. In this work, we begin by presenting our systemic study of the impact that graph structure and attribute auto-correlation on the task of node classification using collective inference. This is the first time such an extensive study has been done. We take advantage of a recently developed method that samples attributed networks—although static—with varying network structure jointly with correlated attributes. We find that the graph connectivity that contributes to the network auto-correlation (i.e., the local relationships of nodes) and density have the highest impact on the performance of collective inference methods.</p> <p><br></p> <p>Most of the literature to date has focused on static representations of networks, partially due to the difficulty of finding readily-available datasets of dynamic networks. Dynamic network generative models can bridge this gap by generating synthetic graphs similar to observed real-world networks. Given that motifs have been established as building blocks for the structure of real-world networks, modeling them can help to generate the graph structure seen and capture correlations in node connections and activity. Therefore, we continue with a study of motif evolution in <em>dynamic</em> temporal graphs. Our key insight is that motifs rarely change configurations in fast-changing dynamic networks (e.g. wedges intotriangles, and vice-versa), but rather keep reappearing at different times while keeping the same configuration. This finding motivates the generative process of our proposed models, using temporal motifs as building blocks, that generates dynamic graphs with links that appear and disappear over time.</p> <p><br></p> <p>Our first proposed model generates dynamic networks based on motif-activity and the roles that nodes play in a motif. For example, a wedge is sampled based on the likelihood of one node having the role of hub with the two other nodes being the spokes. Our model learns all parameters from observed data, with the goal of producing synthetic graphs with similar graph structure and node behavior. We find that using motifs and node roles helps our model generate the more complex structures and the temporal node behavior seen in real-world dynamic networks.</p> <p><br></p> <p>After observing that using motif node-roles helps to capture the changing local structure and behavior of nodes, we extend our work to also consider the attributes generated by nodes’ activities. We propose a second generative model for attributed dynamic networks that (i) captures network structure dynamics through temporal motifs, and (ii) extends the structural roles of nodes in motifs to roles that generate content embeddings. Our new proposed model is the first to generate synthetic dynamic networks and sample content embeddings based on motif node roles. To the best of our knowledge, it is the only attributed dynamic network model that can generate <em>new</em> content embeddings—not observed in the input graph, but still similar to that of the input graph. Our results show that modeling the network attributes with higher-order structures (e.g., motifs) improves the quality of the networks generated.</p> <p><br></p> <p>The generative models proposed address the difficulty of finding readily-available datasets of dynamic networks—attributed or not. This work will also allow others to: (i) generate networks that they can share without divulging individual’s private data, (ii) benchmark model performance, and (iii) explore model generalization on a broader range of conditions, among other uses. Finally, the evaluation measures proposed will elucidate models, allowing fellow researchers to push forward in these domains.</p>