Academic literature on the topic 'Graph Mining'

Frequent sub-graph mining (FSM) is a alternative of frequent pattern mining where patterns are graphs. Among the entities, graph based representation is utilized to effectively represent the complex relationships. Various graph mining techniques are developed from the past many years, most the challenging tasks in graph mining is frequent sub-graph mining (FSM). In FSM many of the existing algorithms consider only graph based structure, the relationships based on entities involved and strength is not considered. It is very important to handle the complex and huge data. There is very huge demand in distributed computational approaches. In this paper, An Ensemble Distributed Search-FSGM-CRD Compressed Cache Algorithm is developed and implemented to find frequent sub graphs

Frequent subgraph mining (FSM) is an essential and challenging graph mining task used in several applications of the modern data science. Some of the FSM algorithms have the objective of finding all frequent subgraphs whereas some of the algorithms focus on discovering frequent subgraphs approximately. On the other hand, modern applications employ evolving graphs where the increments are small graphs or stream of nodes and edges. In such cases, FSM task becomes more challenging due to growing data size and complexity of the base algorithms. Recently we see frequent subgraph mining algorithms designed for dynamic graph data. However, there is no comparative review of the dynamic subgraph mining algorithms focusing on the discovery of frequent subgraphs over evolving graph data. This article focuses on the characteristics of dynamic frequent subgraph mining algorithms over evolving graphs. We first introduce and compare dynamic frequent subgraph mining algorithms; trying to highlight their attributes as increment type, graph type, graph representation, internal data structure, algorithmic approach, programming approach, base algorithm and output type. Secondly, we introduce and compare the approximate frequent subgraph mining algorithms for dynamic graphs with additional attributes as their sampling strategy, data in the sample, statistical guarantees on the sample and their main objective. Finally, we highlight research opportunities in this specific domain from our perspective. Overall, we aim to introduce the research area of frequent subgraph mining over evolving graphs with the hope that this can serve as a reference and inspiration for the researchers of the field.

Attack graph modeling aims to generate attack models by investigating attack behaviors recorded in intrusion alerts raised in network security devices. Attack models can help network security administrators discover an attack strategy that intruders use to compromise the network and implement a timely response to security threats. However, the state-of-the-art algorithms for attack graph modeling are unable to obtain a high-level or global-oriented view of the attack strategy. To address the aforementioned issue, considering the similarity between attack behavior and workflow, we employ a heuristic process mining algorithm to generate the initial attack graph. Although the initial attack graphs generated by the heuristic process mining algorithm are complete, they are extremely complex for manual analysis. To improve their readability, we propose a graph segmentation algorithm to split a complex attack graph into multiple subgraphs while preserving the original structure. Furthermore, to handle massive volume alert data, we propose a distributed attack graph generation algorithm based on Hadoop MapReduce and a distributed attack graph segmentation algorithm based on Spark GraphX. Additionally, we conduct comprehensive experiments to validate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms achieve considerable improvement over comparative algorithms in terms of accuracy and efficiency.

Into the data mining field, frequent approximate subgraph (FAS) mining has become an important technique with a broad spectrum of real-life applications. This fact is because several real-life phenomena can be modeled by graphs. In the literature, several algorithms have been reported for mining frequent approximate patterns on simple-graph collections; however, there are applications where more complex data structures, as multi-graphs, are needed for modeling the problem. But to the best of our knowledge, there is no FAS mining algorithm designed for dealing with multi-graphs. Therefore, in this paper, a canonical form (CF) for simple-graphs is extended to allow representing multi-graphs and a state-of-the-art algorithm for FAS mining is also extended for processing multi-graph collections by using the extended CF. Our experiments over different synthetic and real-world multi-graph collections show that the proposed algorithm has a good performance in terms of runtime and scalability. Additionally, we show the usefulness of the patterns computed by our algorithm in an image classification problem where images are represented as multi-graphs.

Knowledge extraction is very much possible from the community graph using graph mining techniques. The authors have studied the related definitions of graph partition in terms of both mathematical as well as computational aspects. To derive knowledge from a particular sub-community graph of a large community graph, the authors start partitioning the large community graph into smaller sub-community graphs. Thus, the knowledge extraction from the sub-community graph becomes easier and faster. The proposed approach of partition is done by detection of edges among the community members of dissimilar community. By studying existing techniques followed by different researchers, the authors propose a new and simple algorithm for partitioning the community graph into sub-community graphs using graph mining techniques. Finally, the authors have considered a benchmark dataset as example which verifies the strength and easiness of the proposed algorithm.

Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.

Due to rapid development of the Internet technology and new scientific advances, the number of applications that model the data as graphs increases, because graphs have highly expressive power to model a complicated structure. Graph mining is a well-explored area of research which is gaining popularity in the data mining community. A graph is a general model to represent data and has been used in many domains such as cheminformatics, web information management system, computer network, and bioinformatics, to name a few. In graph mining the frequent subgraph discovery is a challenging task. Frequent subgraph mining is concerned with discovery of those subgraphs from graph dataset which have frequent or multiple instances within the given graph dataset. In the literature a large number of frequent subgraph mining algorithms have been proposed; these included FSG, AGM, gSpan, CloseGraph, SPIN, Gaston, and Mofa. The objective of this research work is to perform quantitative comparison of the above listed techniques. The performances of these techniques have been evaluated through a number of experiments based on three different state-of-the-art graph datasets. This novel work will provide base for anyone who is working to design a new frequent subgraph discovery technique.

Real world data from various application domains can be modeled as a graph, e.g. social networks and biomedical networks like protein interaction networks or co-activation networks of brain regions. A graph is a powerful concept to model arbitrary (structural) relationships among objects. In recent years, the prevalence of social networks has made graph mining an important center of attention in the data mining field. There are many important tasks in graph mining, such as graph clustering, outlier detection, and link prediction. Many algorithms have been proposed in the literature to solve these tasks. However, normally these issues are solved separately, although they are closely related. Detecting and exploiting the relationship among them is a new challenge in graph mining. Moreover, with data explosion, more information has already been integrated into graph structure. For example, bipartite graphs contain two types of node and graphs with node attributes offer additional non-structural information. Therefore, more challenges arise from the increasing graph complexity. This thesis aims to solve these challenges in order to gain new knowledge from graph data. An important paradigm of data mining used in this thesis is the principle of Minimum Description Length (MDL). It follows the assumption: the more knowledge we have learned from the data, the better we are able to compress the data. The MDL principle balances the complexity of the selected model and the goodness of fit between model and data. Thus, it naturally avoids over-fitting. This thesis proposes several algorithms based on the MDL principle to acquire knowledge from various types of graphs: Info-spot (Automatically Spotting Information-rich Nodes in Graphs) proposes a parameter-free and efficient algorithm for the fully automatic detection of interesting nodes which is a novel outlier notion in graph. Then in contrast to traditional graph mining approaches that focus on discovering dense subgraphs, a novel graph mining technique CXprime (Compression-based eXploiting Primitives) is proposed. It models the transitivity and the hubness of a graph using structure primitives (all possible three-node substructures). Under the coding scheme of CXprime, clusters with structural information can be discovered, dominating substructures of a graph can be distinguished, and a new link prediction score based on substructures is proposed. The next algorithm SCMiner (Summarization-Compression Miner) integrates tasks such as graph summarization, graph clustering, link prediction, and the discovery of the hidden structure of a bipartite graph on the basis of data compression. Finally, a method for non-redundant graph clustering called IROC (Information-theoretic non-Redundant Overlapping Clustering) is proposed to smartly combine structural information with non-structural information based on MDL. IROC is able to detect overlapping communities within subspaces of the attributes. To sum up, algorithms to unify different learning tasks for various types of graphs are proposed. Additionally, these algorithms are based on the MDL principle, which facilitates the unification of different graph learning tasks, the integration of different graph types, and the automatic selection of input parameters that are otherwise difficult to estimate.

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 distributed graph processing is to correctly partition the graph data between different machine. 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.
Con el reciente crecimiento de las redes sociales y el deseo humano de interactuar con el mundo digital, una gran cantidad de datos de interacción humano-a-humano o humano-a-dispositivo se generan cada segundo. Con el auge de los dispositivos IoT, las interacciones dispositivo-a-dispositivo también están en alza. Todas estas interacciones no son más que una representación de como la red subyacente conecta distintas entidades en el tiempo. Modelar estas interacciones en forma de red de interacciones presenta una gran cantidad de oportunidades únicas para descubrir patrones interesantes y entender la dinamicidad de la red. Entender la dinamicidad de la red es clave ya que encapsula la forma en la que nos comunicamos, socializamos, consumimos información y somos influenciados. Para ello, en esta tesis doctoral, nos centramos en analizar una red de interacciones para entender como la red subyacente es usada. Definimos una red de interacciones como una sequencia de interacciones grabadas en el tiempo E sobre aristas de un grafo estático G=(V, E). Las redes de interacción se pueden usar para modelar gran cantidad de aplicaciones reales, por ejemplo en una red social o de comunicaciones cada interacción sobre una arista representa una interacción entre dos usuarios (correo electrónico, llamada, retweet), o en el caso de una red financiera una interacción entre dos cuentas para representar una transacción. Analizamos las redes de interacción bajo múltiples escenarios. En el primero, estudiamos las redes de interacción bajo un modelo de ventana deslizante. Asumimos que un nodo puede mandar información a otros nodos si estan conectados utilizando aristas presentes en una ventana temporal. En este modelo, estudiamos como la importancia o centralidad de un nodo evoluciona en el tiempo. En el segundo escenario añadimos restricciones adicionales respecto como la información fluye entre nodos. Asumimos que un nodo puede mandar información a otros nodos solo si existe un camino temporal entre ellos. Para restringir la longitud de los caminos temporales también asumimos una ventana temporal. Aplicamos este modelo para resolver este problema de maximización de influencia restringido temporalmente. Analizando los datos de la red de interacción bajo nuestro modelo intentamos descubrir los k nodos más influyentes. Examinamos nuestro modelo en interacciones humano-a-humano, usando datos de redes sociales, como en ubicación-a-ubicación usando datos de redes sociales basades en localización (LBSNs). En el mismo escenario también minamos camínos cíclicos temporales para entender los patrones de comunicación en una red. Existen múltiples aplicaciones para cíclos temporales y aparecen naturalmente en redes de comunicación donde una persona envía un mensaje y después de un tiempo reacciona a una cadena de reacciones de compañeros en el mensaje. En redes financieras, por otro lado, la presencia de un ciclo temporal puede indicar ciertos tipos de fraude. Proponemos algoritmos eficientes para todos nuestros análisis y evaluamos su eficiencia y efectividad en datos reales. Finalmente, dado que muchos de los algoritmos estudiados tienen una gran demanda computacional, también estudiamos los algoritmos de procesado distribuido de grafos. Un aspecto importante de procesado distribuido de grafos es el de correctamente particionar los datos del grafo entre distintas máquinas. Gran cantidad de investigación se ha realizado en estrategias para particionar eficientemente un grafo, pero no existe un particionamento bueno para todos los tipos de grafos y algoritmos. Escoger la mejor estrategia de partición no es trivial y es mayoritariamente un ejercicio de prueba y error. Con tal de abordar este problema, proporcionamos un modelo de costes para dar un mejor entendimiento en como una estrategia de particionamiento actúa dado un grafo y un algoritmo.

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

We investigate the applicability of network analysis to the problem of finding seminal publications in scientific publishing. In particular, we focus on the network measures betweenness centrality, the so-called backbone graph, and the burstiness of citations. The metrics are evaluated using precision-related scores with respect to gold standards based on fellow programmes and manual annotation. Citation counts, PageRank, and random selection are used as baselines. We find that the backbone graph provides us with a way to possibly discover seminal publications with low citation count, and combining betweenness and burstiness gives results on par with citation count.
I detta examensarbete undersöks det huruvida analys av citeringsgrafer kan användas för att finna betydelsefulla vetenskapliga publikationer. Framför allt studeras ”betweenness”-centralitet, den så kallade ”backbone”-grafen samt ”burstiness” av citeringar. Dessa mått utvärderas med hjälp av precisionsmått med avseende på guldstandarder baserade på ’fellow’-program samt via manuell annotering. Antal citeringar, PageRank, och slumpmässigt urval används som jämförelse. Resultaten visar att ”backbone”-grafen kan bidra till att eventuellt upptäcka betydelsefulla publikationer med ett lågt antal citeringar samt att en kombination av ”betweenness” och ”burstiness” ger resultat i nivå med de man får av att räkna antal citeringar.

Détecter et suivre les objets principaux d’une vidéo est une étape nécessaire en vue d’en décrire le contenu pour, par exemple, permettre une indexation judicieuse des données multimédia par les moteurs de recherche. Les techniques de suivi d’objets actuelles souffrent de défauts majeurs. En effet, soit elles nécessitent que l’utilisateur désigne la cible a suivre, soit il est nécessaire d’utiliser un classifieur pré-entraîné à reconnaitre une classe spécifique d’objets, comme des humains ou des voitures. Puisque ces méthodes requièrent l’intervention de l’utilisateur ou une connaissance a priori du contenu traité, elles ne sont pas suffisamment génériques pour être appliquées aux vidéos amateurs telles qu’on peut en trouver sur YouTube. Pour résoudre ce problème, nous partons de l’hypothèse que, dans le cas de vidéos dont l’arrière-plan n’est pas fixe, celui-ci apparait moins souvent que les objets intéressants. De plus, dans une vidéo, la topologie des différents éléments visuels composant un objet est supposée consistante d’une image a l’autre. Nous représentons chaque image par un graphe plan modélisant sa topologie. Ensuite, nous recherchons des motifs apparaissant fréquemment dans la base de données de graphes plans ainsi créée pour représenter chaque vidéo. Cette approche nous permet de détecter et suivre les objets principaux d’une vidéo de manière non supervisée en nous basant uniquement sur la fréquence des motifs. Nos contributions sont donc réparties entre les domaines de la fouille de graphes et du suivi d’objets. Dans le premier domaine, notre première contribution est de présenter un algorithme de fouille de graphes plans efficace, appelé PLAGRAM. Cet algorithme exploite la planarité des graphes et une nouvelle stratégie d’extension des motifs. Nous introduisons ensuite des contraintes spatio-temporelles au processus de fouille afin d’exploiter le fait que, dans une vidéo, les objets se déplacent peu d’une image a l’autre. Ainsi, nous contraignons les occurrences d’un même motif a être proches dans l’espace et dans le temps en limitant le nombre d’images et la distance spatiale les séparant. Nous présentons deux nouveaux algorithmes, DYPLAGRAM qui utilise la contrainte temporelle pour limiter le nombre de motifs extraits, et DYPLAGRAM_ST qui extrait efficacement des motifs spatio-temporels fréquents depuis les bases de données représentant les vidéos. Dans le domaine du suivi d’objets, nos contributions consistent en deux approches utilisant les motifs spatio-temporels pour suivre les objets principaux dans les vidéos. La première est basée sur une recherche du chemin de poids minimum dans un graphe connectant les motifs spatio-temporels tandis que l’autre est basée sur une méthode de clustering permettant de regrouper les motifs pour suivre les objets plus longtemps. Nous présentons aussi deux applications industrielles de notre méthode
Detecting and following the main objects of a video is necessary to describe its content in order to, for example, allow for a relevant indexation of the multimedia content by the search engines. Current object tracking approaches either require the user to select the targets to follow, or rely on pre-trained classifiers to detect particular classes of objects such as pedestrians or car for example. Since those methods rely on user intervention or prior knowledge of the content to process, they cannot be applied automatically on amateur videos such as the ones found on YouTube. To solve this problem, we build upon the hypothesis that, in videos with a moving background, the main objects should appear more frequently than the background. Moreover, in a video, the topology of the visual elements composing an object is supposed consistent from one frame to another. We represent each image of the videos with plane graphs modeling their topology. Then, we search for substructures appearing frequently in the database of plane graphs thus created to represent each video. Our contributions cover both fields of graph mining and object tracking. In the first field, our first contribution is to present an efficient plane graph mining algorithm, named PLAGRAM. This algorithm exploits the planarity of the graphs and a new strategy to extend the patterns. The next contributions consist in the introduction of spatio-temporal constraints into the mining process to exploit the fact that, in a video, the motion of objects is small from on frame to another. Thus, we constrain the occurrences of a same pattern to be close in space and time by limiting the number of frames and the spatial distance separating them. We present two new algorithms, DYPLAGRAM which makes use of the temporal constraint to limit the number of extracted patterns, and DYPLAGRAM_ST which efficiently mines frequent spatio-temporal patterns from the datasets representing the videos. In the field of object tracking, our contributions consist in two approaches using the spatio-temporal patterns to track the main objects in videos. The first one is based on a search of the shortest path in a graph connecting the spatio-temporal patterns, while the second one uses a clustering approach to regroup them in order to follow the objects for a longer period of time. We also present two industrial applications of our method

Powered by big data infrastructures, social network platforms are gathering data on many aspects of our daily lives. The online social world is reflecting our physical world in an increasingly detailed way by collecting people's individual biographies and their various of relationships with other people. Although massive amount of social data has been gathered, an urgent challenge remain unsolved, which is to discover meaningful knowledge that can empower the social platforms to really understand their users from different perspectives.

Motivated by this trend, my research addresses the reasoning and mathematical modeling behind interesting phenomena on social networks. Proposing graph based data mining framework regarding to heterogeneous data sources is the major goal of my research. The algorithms, by design, utilize graph structure with heterogeneous link and node features to creatively represent social networks' basic structures and phenomena on top of them.

The graph based heterogeneous mining methodology is proved to be effective on a series of knowledge discovery topics, including network structure and macro social pattern mining such as magnet community detection (87), social influence propagation and social similarity mining (85), and spam detection (86). The future work is to consider dynamic relation on social data mining and how graph based approaches adapt from the new situations.

L'étude et l'analyse des réseaux sociaux attirent l'attention d'une variété de sciences (psychologie, statistiques, sociologie). Parmi elles, le domaine de la fouille de données offre des outils pour extraire automatiquement des informations utiles sur les propriétés de ces réseaux. Plus précisément, la fouille de graphes répond au besoin de modéliser et d'étudier les réseaux sociaux en particulier dans le cas des grandes communautés que l'on trouve habituellement dans les médias en ligne oú la taille des réseaux sociaux est trop grande pour les méthodes manuelles. La modélisation générale d'un réseau social est basée sur des structures de graphes. Les sommets du graphe représentent les individus et les arêtes des actions différentes ou des types de liens sociaux entre les individus. Une communauté est définie comme un sous-graphe (d'un réseau social) et se caractérise par des liens denses. Plusieurs mesures ont été précédemment proposées pour l'évaluation des divers aspects de la qualité de ces communautés mais la plupart d'entre elles ignorent diverses propriétés des interactions entre individus (par exemple l'orientation de ces liens). Dans la recherche présentée ici, le concept de "k-core" est utilisé comme un moyen d'évaluer les communautés et d'en extraire des informations. La structure de "k-core" mesure la robustesse d'un réseau non orienté en utilisant la dégénérescence du graphe. En outre, des extensions du principe de dégénérescence sont introduites pour des réseaux dont les arêtes possèdent plus d'informations que celles non orientées. Le point de départ est l'exploration des attributs qui peuvent être extraits des graphes non orientés (réseaux sociaux). Sur ce point, la dégénérescence est utilisée pour évaluer les caractéristiques d'une collaboration entre individus et sur l'ensemble de la communauté - une propriété non capturée par les métriques sur les sommets individuels ou par les métriques d'évaluation communautaires traditionnelles. Ensuite, cette méthode est étendue aux graphes pondérés, orientés et signés afin d'offrir de nouvelles mesures d'évaluation pour les réseaux sociaux. Ces nouvelles fonctionnalités apportent des outils de mesure de la collaboration dans les réseaux sociaux oú l'on peut attribuer un poids ou un orientation à une interaction et fournir des moyens alternatifs pour capturer l'importance des individus au sein d'une communauté. Pour les graphes signés, l'extension de la dégénérescence permet de proposer des métriques supplémentaires qui peuvent être utilisées pour modéliser la confiance. De plus, nous introduisons une approche de partitionnement basée sur le traitement du graphe de manière hiérarchique, hiérarchie fournie par le principe de "core expansion sequence" qui partitionne le graphe en différents niveaux ordonnés conformément à la décomposition "k-core". Les modèles théoriques de graphes sont ensuite appliqués sur des graphes du monde réel pour examiner les tendances et les comportements. Les jeux de données explorés incluent des graphes de collaborations scientifiques et des graphes de citations (DBLP et ARXIV), une instance de graphe interne de Wikipédia et des réseaux basés sur la confiance entre les individus (par exemple Epinions et Slashdot). Les conclusions sur ces ensembles de données sont significatives et les modèles proposés offrent des résultats intuitifs
The study and analysis of social networks attract attention from a variety of Sciences (psychology, statistics, sociology). Among them, the field of Data Mining offers tools to automatically extract useful information on properties of those networks. More specifically, Graph Mining serves the need to model and investigate social networks especially in the case of large communities - usually found in online media - where social networks are prohibitively large for non-automated methodologies. The general modeling of a social network is based on graph structures. Nodes of the graph represent individuals and edges signify different actions or types of social connections between them. A community is defined as a subgraph (of a social network) and is characterized by dense connections. Various measures have been proposed to evaluate different quality aspects of such communities - in most cases ignoring various properties of the connections (e. G. Directionality). In the work presented here, the k-core concept is used as a means to evaluate communities and extract information. The k-core structure essentially measures the robustness of an undirected network through degeneracy. Further more extensions of degeneracy are introduced to networks that their edges offer more information than the undirected type. Starting point is the exploration of properties that can be extracted from undirected graphs (of social networks). On this, degeneracy is used to evaluate collaboration features - a property not captured by the single node metrics or by the established community evaluation metrics - of both individuals and the entire community. Next, this process is extended for weighted, directed and signed graphs offering a plethora of novel evaluation metrics for social networks. These new features offer measurement tools for collaboration in social networks where we can assign a weight or a direction to a connection and provide alternative ways to signify the importance of individuals within a community. For signed graphs the extension of degeneracy offers additional metrics that can be used for trust management. Moreover, a clustering approach is introduced which capitalizes on processing the graph in a hierarchical manner provided by its core expansion sequence, an ordered partition of the graph into different levels according to the k-core decomposition The graph theoretical models are then applied in real world graphs to investigate trends and behaviors. The datasets explored include scientific collaboration and citation graphs (DBLP and ARXIV), a snapshot of Wikipedia's inner graph and trust networks (e. G. Epinions and Slashdot). The findings on these datasets are interesting and the proposed models offer intuitive results

Depuis l'invention du PageRank par Google pour les requêtes Web à la fin des années 1990, les algorithmes de graphe font partie de notre quotidien. Au milieu des années 2000, l'arrivée des réseaux sociaux a amplifié ce phénomène, élargissant toujours plus les cas d'usage de ces algorithmes. Les relations entre entités peuvent être de multiples sortes : relations symétriques utilisateur-utilisateur pour Facebook ou LinkedIn, relations asymétriques follower-followee pour Twitter, ou encore, relations bipartites utilisateur-contenu pour Netflix ou Amazon. Toutes soulèvent des problèmes spécifiques et les applications sont nombreuses : calcul de centralité pour la mesure d'influence, le partitionnement de nœuds pour la fouille de données, la classification de nœuds pour les recommandations ou l'embedding pour la prédiction de liens en sont quelques exemples.En parallèle, les conditions d'utilisation des algorithmes de graphe sont devenues plus contraignantes. D'une part, les jeux de données toujours plus gros avec des millions d'entités et parfois des milliards de relations limite la complexité asymptotique des algorithmes pour les applications industrielles. D'autre part, dans la mesure où ces algorithmes influencent nos vies, les exigences d'explicabilité et d'équité dans le domaine de l'intelligence artificielle augmentent. Les algorithmes de graphe ne font pas exception à la règle. L'Union européenne a par exemple publié un guide de conduite pour une IA fiable. Ceci implique de pousser encore plus loin l'analyse des modèles actuels, voire d'en proposer de nouveaux.Cette thèse propose des réponses ciblées via l'analyse d'algorithmes classiques, mais aussi de leurs extensions et variantes, voire d'algorithmes originaux. La capacité à passer à l'échelle restant un critère clé. Dans le sillage de ce que le projet Scikit-learn propose pour l'apprentissage automatique sur données vectorielles, nous estimons qu'il est important de rendre ces algorithmes accessibles au plus grand nombre et de démocratiser la manipulation de graphes. Nous avons donc développé un logiciel libre, Scikit-network, qui implémente et documente ces algorithmes de façon simple et efficace. Grâce à cet outil, nous pouvons explorer plusieurs tâches classiques telles que l'embedding de graphe, le partitionnement, ou encore la classification semi-supervisée
Since the introduction of Google's PageRank method for Web searches in the late 1990s, graph algorithms have been part of our daily lives. In the mid 2000s, the arrival of social networks has amplified this phenomenon, creating new use-cases for these algorithms. Relationships between entities can be of multiple types: user-user symmetric relationships for Facebook or LinkedIn, follower-followee asymmetric ones for Twitter or even user-content bipartite ones for Netflix or Amazon. They all come with their own challenges and the applications are numerous: centrality calculus for influence measurement, node clustering for knowledge discovery, node classification for recommendation or embedding for link prediction, to name a few.In the meantime, the context in which graph algorithms are applied has rapidly become more constrained. On the one hand, the increasing size of the datasets with millions of entities, and sometimes billions of relationships, bounds the asymptotic complexity of the algorithms for industrial applications. On the other hand, as these algorithms affect our daily lives, there is a growing demand for explanability and fairness in the domain of artificial intelligence in general. Graph mining is no exception. For example, the European Union has published a set of ethics guidelines for trustworthy AI. This calls for further analysis of the current models and even new ones.This thesis provides specific answers via a novel analysis of not only standard, but also extensions, variants, and original graph algorithms. Scalability is taken into account every step of the way. Following what the Scikit-learn project does for standard machine learning, we deem important to make these algorithms available to as many people as possible and participate in graph mining popularization. Therefore, we have developed an open-source software, Scikit-network, which implements and documents the algorithms in a simple and efficient way. With this tool, we cover several areas of graph mining such as graph embedding, clustering, and semi-supervised node classification

Food is an essential to our existence but under certain conditions it could become the origin to the accumulative health damages. Technological processes as heating, chopping, mincing, grounding, promote the lipid oxidation process in muscle tissues and meat foodstuffs. Lipid oxidation occurred rapidly in turkey muscle, intermediate in duck, and slowest in chicken during frozen storage. Depletion of tocopherol during frozen storage was more rapid in turkey and duck compared to chicken. These processes developed from lipid peroxides produce many cytotoxic compounds including malondialdehyde (MDA). The muscle tissue is further oxidized in stomach conditions producing additional cytotoxic compounds. Oxidized lipids that are formed during digestion of a meal possess the potential to promote reactions that incur vascular diseases. A grape seed extract (1% of the meat weight) and butylated hydroxytoluene (0.2% of the lipid weight) were each effective at preventing formation of lipid oxidation products for 3 hours during co-incubation with cooked turkey meat in simulated gastric fluid (SGF). Polyphenols in the human diet, as an integral part of the meal prevent the generation and absorption of cytotoxic compounds and the destruction of essential nutrients, eg. antioxidants vitamins during the meal. Polyphenols act as antioxidants in the gastrointestinal tract; they scavenge free radicals and may interact with reactive carbonyls, enzymes and proteins. These all reactions results in decreasing the absorption of reactive carbonyls and possible other cytotoxic compounds into the plasma. Consumptions of diet high in fat and red meat are contributory risk factors partly due to an increase production of cytotoxic oxidized lipid products eg. MDA. However, the simultaneously consumption of polyphenols rich foods reduce these factors. Locating the biological site of action of polyphenols in the in the gastrointestinal tract may explain the paradox between the protective effect of a highly polyphenols rich diet and the low bioavailability of these molecules in human plasma. It may also explain the "French paradox" and the beneficial effect of Mediterranean and Japanese diets, in which food products with high antioxidants content such as polyphenols are consumed during the meal.

Uncertainty exists widely in practical engineering. It is an important challenge in engineering structural analysis. In truss structures, the uncertainties of axial stiffness of bolted joints will significantly affect the mechanical behavior of the structure as the axial load is dominated by the member internal forces. Structural response analysis based on determined structural parameters is a common forward problem that can be solved by modeling analysis methods. However, the uncertainties parameter of axial stiffness of bolted joint cannot be determined during the design and analysis of truss structure in the direct nonlinear analysis method. Structural parameter identification based on structural response is a typical inverse problem in engineering, which is difficult to solve using traditional analysis tools. In this paper, an inverse model based on Graph Neural Network (GNN) is proposed. The feature encoding method for transforming truss structures into graph representations of GNN is defined. A parameterized acquisition method for large-scale datasets is presented, and an innovative inversion model based on GNN for the inversion of uncertain parameters of truss structures is proposed. The proposed method is shown to perform well with an inversion accuracy, and accurate results can be obtained with limited data sets. The inversion method has strong data mining capability and model interpretability, making it a promising direction for exploring engineering structural analysis.

1. Macroeconomic Summary In December, headline inflation (13.1%) and the average of the core inflation measures (10.3%) continued to trend upward, posting higher rates than those estimated by the Central Bank's technical staff and surpassing the market average. Inflation expectations for all terms exceeded the 3.0% target. In that month, every major group in the Consumer Price Index (CPI) registered higher-than-estimated increases, and the diffusion indicators continued to show generalized price hikes. Accumulated exchange rate pressures on prices, indexation to high inflation rates, and several food supply shocks would explain, in part, the acceleration in inflation. All of this is in a context of significant surplus demand, a tight labor market, and inflation expectations at different terms that exceed the 3.0% target. Compared to the October edition of the Monetary Policy Report, the forecast path for headline and core inflation (excluding food and regulated items: EFR) increased (Graphs 1.1 and 1.2), reflecting heightened accumulated exchange rate pressures, price indexation to a higher inflation rate (CPI and the producer price index: PPI), and the rise in labor costs attributed to a larger-than-estimated adjustment in the minimum wage. Nevertheless, headline inflation is expected to begin to ease by early 2023, although from a higher level than had been estimated in October. This would be supported initially by the slowdown forecast for the food CPI due to a high base of comparison, the end anticipated for the shocks that have affected the prices of these products, and the estimated improvement in external and domestic supply in this sector. In turn, the deterioration in real household income because of high inflation and the end of the effects of pent-up demand, plus tighter external and domestic financial conditions would contribute to diluting surplus demand in 2023 and reducing inflation. By the end of 2023, both headline and core (EFR) inflation would reach 8.7% and would be 3.5% and 3.8%, respectively, by December 2024. These forecasts are subject to a great deal of uncertainty, especially concerning the future behavior of international financial conditions, the evolution of the exchange rate, the pace of adjustment in domestic demand, the extent of indexation of nominal contracts, and the decisions taken regarding the domestic price of fuel and electricity. In the third quarter, economic activity surprised again on the upside and the growth projection for 2022 rose to 8.0% (previously 7.9%). However, it declined to 0.2% for 2023 (previously 0.5%). With this, surplus demand continues to be significant and is still expected to weaken during the current year. Annual economic growth in the third quarter (7.1 % SCA)1 was higher than estimated in October (6.4 % SCA), given stronger domestic demand specifically because of higher-than-expected investment. Private consumption fell from the high level witnessed a quarter earlier and net exports registered a more negative contribution than anticipated. For the fourth quarter, economic activity indicators suggest that gross domestic product (GDP) would have remained high and at a level similar to that observed in the third quarter, with an annual variation of 4.1%. Domestic demand would have slowed in annual terms, although at levels that would have remained above those for output, mainly because of considerable private consumption. Investment would have declined slightly to a value like the average observed in 2019. The real trade deficit would have decreased due to a drop in imports that was more pronounced than the estimated decline in exports. On the forecast horizon, consumption is expected to decline from current elevated levels, partly because of tighter domestic financial conditions and a deterioration in real income due to high inflation. Investment would also weaken and return to levels below those seen before the pandemic. In real terms, the trade deficit would narrow due to a lower momentum projection for domestic demand and higher cumulative real depreciation. In sum, economic growth for all of 2022, 2023, and 2024 would stand at 8.0%, 0.2% and 1.0%, respectively (Graph 1.3). Surplus demand remains high (as measured by the output gap) and is expected to decline in 2023 and could turn negative in 2024 (Graph 1.4). Although the macroeconomic forecast includes a marked slowdown in the economy, an even greater adjustment in domestic absorption cannot be ruled out due to the cumulative effects of tighter external and domestic financial conditions, among other reasons. These estimates continue to be subject to a high degree of uncertainty, which is associated with factors such as global political tensions, changes in international interest rates and their effects on external demand, global risk aversion, the effects of the approved tax reform, the possible impact of reforms announced for this year (pension, health, and labor reforms, among others), and future measures regarding hydrocarbon production. In 2022, the current account deficit would have been high (6.3 % of GDP), but it would be corrected significantly in 2023 (to 3.9 % of GDP) given the expected slowdown in domestic demand. Despite favorable terms of trade, the high external imbalance that would occur during 2022 would be largely due to domestic demand growth, cost pressures associated with high freight rates, higher external debt service payments, and good performance in terms of the profits of foreign companies.2 By 2023, the adjustment in domestic demand would be reflected in a smaller current account deficit especially due to fewer imports, a global moderation in prices and cost pressures, and a reduction in profits remitted abroad by companies with foreign direct investment (FDI) focused on the local market. Despite this anticipated correction in the external imbalance, its level as a percentage of GDP would remain high in the context of tight financial conditions. In the world's main economies, inflation forecasts and expectations point to a reduction by 2023, but at levels that still exceed their central banks' targets. The path anticipated for the Federal Reserve (Fed) interest rate increased and the forecast for global growth continues to be moderate. In the fourth quarter of 2022, logistics costs and international prices for some foods, oil and energy declined from elevated levels, bringing downward pressure to bear on global inflation. Meanwhile, the higher cost of financing, the loss of real income due to high levels of global inflation, and the persistence of the war in Ukraine, among other factors, have contributed to the reduction in global economic growth forecasts. In the United States, inflation turned out to be lower than estimated and the members of the Federal Open Market Committee (FOMC) reduced the growth forecast for 2023. Nevertheless, the actual level of inflation in that country, its forecasts, and expectations exceed the target. Also, the labor market remains tight, and fiscal policy is still expansionary. In this environment, the Fed raised the expected path for policy interest rates and, with this, the market average estimates higher levels for 2023 than those forecast in October. In the region's emerging economies, country risk premia declined during the quarter and the currencies of those countries appreciated against the US dollar. Considering all the above, for the current year, the Central Bank's technical staff increased the path estimated for the Fed's interest rate, reduced the forecast for growth in the country's external demand, lowered the expected path of oil prices, and kept the country’s risk premium assumption high, but at somewhat lower levels than those anticipated in the previous Monetary Policy Report. Moreover, accumulated inflationary pressures originating from the behavior of the exchange rate would continue to be important. External financial conditions facing the economy have improved recently and could be associated with a more favorable international context for the Colombian economy. So far this year, there has been a reduction in long-term bond interest rates in the markets of developed countries and an increase in the prices of risky assets, such as stocks. This would be associated with a faster-than-expected reduction in inflation in the United States and Europe, which would allow for a less restrictive course for monetary policy in those regions. In this context, the risks of a global recession have been reduced and the global appetite for risk has increased. Consequently, the risk premium continues to decline, the Colombian peso has appreciated significantly, and TES interest rates have decreased. Should this trend consolidate, exchange rate inflationary pressures could be less than what was incorporated into the macroeconomic forecast. Uncertainty about external forecasts and their impact on the country remains high, given the unpredictable course of the war in Ukraine, geopolitical tensions, local uncertainty, and the extensive financing needs of the Colombian government and the economy. High inflation with forecasts and expectations above 3.0%, coupled with surplus demand and a tight labor market are compatible with a contractionary stance on monetary policy that is conducive to the macroeconomic adjustment needed to mitigate the risk of de-anchoring inflation expectations and to ensure that inflation converges to the target. Compared to the forecasts in the October edition of the Monetary Policy Report, domestic demand has been more dynamic, with a higher observed level of output exceeding the productive capacity of the economy. In this context of surplus demand, headline and core inflation continued to trend upward and posted surprising increases. Observed and expected international interest rates increased, the country’s risk premia lessened (but remains at high levels), and accumulated exchange rate pressures are still significant. The technical staff's inflation forecast for 2023 increased and inflation expectations remain well above 3.0%. All in all, the risk of inflation expectations becoming unanchored persists, which would accentuate the generalized indexation process and push inflation even further away from the target. This macroeconomic context requires consolidating a contractionary monetary policy stance that aims to meet the inflation target within the forecast horizon and bring the economy's output to levels closer to its potential. 1.2 Monetary Policy Decision At its meetings in December 2022 and January 2023, Banco de la República’s Board of Directors (BDBR) agreed to continue the process of normalizing monetary policy. In December, the BDBR decided by a majority vote to increase the monetary policy interest rate by 100 basis points (bps) and in its January meeting by 75 bps, bringing it to 12.75% (Graph 1.5). 1/ Seasonally and calendar adjusted. 2/ In the current account aggregate, the pressures for a higher external deficit come from those companies with FDI that are focused on the domestic market. In contrast, profits in the mining and energy sectors are more than offset by the external revenue they generate through exports. Box 1 - Electricity Rates: Recent Developments and Indexation. Author: Édgar Caicedo García, Pablo Montealegre Moreno and Álex Fernando Pérez Libreros Box 2 - Indicators of Household Indebtedness. Author: Camilo Gómez y Juan Sebastián Mariño