Information contained in chemical compounds, fingerprint databases, social networks, and interactions between websites all have one thing in common: they can be represented as graphs. The need to analyze, compare, and classify graph datasets has become more evident over the last decade. The graph isomorphism problem is known to belong to the NP class, and the subgraph isomorphism problem is known to be an NP-complete problem. Several error-tolerant graph matching techniques have been developed during the last two decades in order to overcome the computational complexity associated with these problems. Some of these techniques rely upon similarity measures based on the topology of the graphs. Random walks and edit distance kernels are examples of such methods. In conjunction with learning algorithms like back-propagation neural networks, k-nearest neighbor, and support vector machines (SVM), these methods provide a way of classifying graphs based on a training set of labeled instances. This thesis presents a novel approach to error-tolerant graph matching based on current flow analysis. Analysis of current flow in electrical networks is a technique that uses the voltages and currents obtained through nodal analysis of a graph representing an electrical circuit. Current flow analysis in electrical networks shares some interesting connections with the number of random walks along the graph. We propose an algorithm to calculate a similarity measure between two graphs based on the current flows along geodesics of the same degree. This similarity measure can be applied over large graph datasets, allowing these datasets to be compared in a reasonable amount of time. This thesis investigates the classification potential of several data mining algorithms based on the information extracted from a graph dataset and represented as current flow vectors. We describe our operational prototype and evaluate its effectiveness on the NCI-HIV dataset.

Za posledné roky je zaznamenaný nárast prác zahrňujúcich komplexnú detekciu malvéru. Pre potreby zachytenia správania je často vhodné pouziť formát grafov. To je prípad antivírusového programu Avast, ktorého behaviorálny štít deteguje škodlivé správanie a ukladá ich vo forme grafov. Keďže sa jedná o proprietárne riešenie a Avast antivirus pracuje s vlastnou sadou charakterizovaného správania bolo nutné navrhnúť vlastnú metódu detekcie, ktorá bude postavená nad týmito grafmi správania. Táto práca analyzuje grafy správania škodlivého softvéru zachytené behavioralnym štítom antivírusového programu Avast pre proces hlbšej detekcie škodlivého softvéru. Detekcia škodlivého správania sa začína analýzou a abstrakciou vzorcov z grafu správania. Izolované vzory môžu efektívnejšie identifikovať dynamicky sa meniaci malware. Grafy správania sú uložené v databáze grafov Neo4j a každý deň sú zachytené tisíce z nich. Cieľom tejto práce bolo navrhnúť algoritmus na identifikáciu správania škodlivého softvéru s dôrazom na rýchlosť skenovania a jasnosť identifikovaných vzorcov správania. Identifikácia škodlivého správania spočíva v nájdení najdôležitejších vlastností natrénovaných klasifikátorov a následnej extrakcie podgrafu pozostávajúceho iba z týchto dôležitých vlastností uzlov a vzťahov medzi nimi. Následne je navrhnuté pravidlo pre hodnotenie extrahovaného podgrafu. Diplomová práca prebehla v spolupráci so spoločnosťou Avast Software s.r.o.