Tsitsiashvili G Sh, Losev A S, Osipova M A and Kharchenko Yu N
Institute for Applied Mathematics FEB RAS, Russia
Posters-Accepted Abstracts: J Appl Computat Math
In this paper, we consider oriented graph with finite sets of nodes and edges. Such graphs appear in a description of protein networks. These graphs may be factorized by the cyclic equivalence and the partial order between equivalence classes may be introduced. A direct way to realize this procedure is the Boolean multiplication of the graph contiguity matrix, but such approach is too complicated. So, we construct a sequential algorithm of an oriented graph factorization with a square number of arithmetical operations by a number of graph nodes. A decrease of the calculation complexity is connected with an introduction of a partial order matrix which is defined recursively by assignment operations. To test suggested factorization algorithm, we consider the protein network Arabidopsis with 2824 nodes and 7500 edges. Using sufficiently powerful server, it is possible to realize the factorization procedure by the calculation of the matrixes during 21 days. Using the sequential algorithm, it is possible to fulfill the factorization procedure on a notebook during one and half hours. An analysis of a distribution of equivalence classes by numbers of their nodes shows that there is the equivalence class (a kernel) with 958 nodes which composes approximately 34 percent of all network vertices.
Tsitsiashvili G Sh has completed his Doctorate thesis on physical and mathematical sciences. He is the Head of IAM FEB RAS laboratory on probability methods and systems analysis and has published more than 100 papers in reputed journals. The main sphere of his researches is applied probability models: queuing, reliability, insurance, epidemic, etc.
Email: guram@iam.dvo.ru
Journal of Applied & Computational Mathematics received 1282 citations as per Google Scholar report
Spanish 
Chinese 
Russian 
German 
French 
Japanese 
Portuguese 
Hindi 