Mining Attribute Evolution Rules In Dynamic Attributed Graphs

Data mining is a research area that aims at discovering interesting information in databases.Various types of data can be analyzed using data mining techniques such as tables from relational databases and text documents.In recent years,graph has attracted the interest of many researchers as one of the complex data structures,which could be found in many emerging domains,such as sensor networks,the internet of things,vehicular networks,social networks,and knowledge graphs.A key task with graphs is pattern mining.It aims at discovering all patterns that meet user-defined criteria like the minimum occurrence frequency in a graph or a graph database.To solve that problem,several algorithms have been proposed.However,most of them assume that graphs are static and vertices are described with a single label.Such assumptions allow to simplify the design of algorithms but greatly restrict their applications.In real life,it is desirable to analyze the evolution properties of graphs with multiple attributes per node.This thesis is dedicated to exploring the evolution and correlation between attributes in dynamic attributed graphs.The word ’attributed’ in the term dynamic attributed graph means that a graph’s vertices have multiple attributes,which can be used to describe them.The word ’dynamic’ means that attribute values,vertices and edges can change over time.For example,in a social network,vertices represent individuals,edges denote relationships,while attribute values may indicate information such as each person’s age,salary and job.In the real world,relationships and attributes of vertices can change over time.This thesis makes two main contributions.The first one is to design techniques for discovering rules that reveal how attributes are changing in a dynamic attributed graph.These rules,called attribute evolution rules,indicate that some change(s)in some attribute(s)of some vertice(s)have a high probability of causing a change(s)for attribute(s)of other vertice(s).An attribute evolution rule thus represents a correlation between attribute values,which follow a strict temporal ordering,and may indicate a potential causality relationship between attributes.The second contribution of this thesis is related to an industrial project on alarm compression in telecommunication networks.Inspired by the above contribution,the alarm compression problem was transformed into a problem of correlation analysis between attributes for a dynamic attributed graph.Alarms on a telecommunication network are viewed as attributes of devices(nodes)that may propagate over telecommunication links(edges).In this industrial project,the timestamps of attributes may be asynchronous.Thus,a novel type of rules called alarm correlation rules was proposed,by drawing inspiration from the proposed attribute evolution rules but weakening the constraint of a strict time ordering.The resulting alarm correlation rules represent a strong correlation between different alarms on different devices in a telecommunication network,and meet the needs of the industrial project(alarm compression and localization).Two corresponding algorithms are proposed and implemented for efficiently discovering the above two pattern types.Both algorithms employ appropriate pruning strategies and optimizations are used to improve the efficiency.Finally,the two algorithms have been evaluated on real datasets,and the experimental results demonstrate the robustness,efficiency,and practicality of the proposed algorithms for mining patterns in dynamic attributed graphs.