Implementation of a Software System for Patterns Identification in a Multigraph Exemplified by an Interbank Lending Network in the Agent Based Model of a Banking System

摘要

A graph is a universal representation of interrelations characterizing different social and economic phenomena. Vertices of a graph represent objects of different kinds and its edges describe interrelations between these objects. Vertices and edges can be characterized by corresponding sets of attributes describing different properties of objects and relations between them. A graph is called a multigraph if its elements are characterized by multiple attributes. In such a case, different phenomena taking place in a system can be described in terms of multigraph's subgraph, or pattern, having particular structure. Then the problem of phenomena (pattern) recognition can be formalized as a problem of subgraph matching. The study presents the software aimed at solution of the problem of subgraph matching in multigraphs. The software is implemented in the multi-agent framework. One of its key structural elements is a knowledge base containing quantitative description of patterns to be matched. The software system contains a set of program agents responsible for searching for the particular patterns. As subgraph matching problem is NP-complete, there is no universal efficient algorithm for matching a pattern having arbitrary structure. Therefore, different search agents may use different algorithms. As a result, the multi-agent architecture is necessary for efficient system implementation usage. In the study, the system operation is exemplified by the search for two different patterns in the interbank network generated by the agent based model of banking system. The first pattern corresponds to the appearance of the Ponzi scheme, and the second one corresponds to the case of cyclical transition of money between three banks. The analysis of dependence between the efficiency of pattern recognition, and the amount of noise in the data is conducted.