Community Detection On Directed Acyclic Networks

A directed acyclic network is a special type of network without cycles,generally existing in the fields of biology,genetics,finance,etc.Community is one of the most prominent structural features on the mesoscopic scale of the network,which has a vital influence on the network function.The detection and analysis of network community structure have become an important topic,attracting the attention of many scholars in different fields.The detection of community structure in directed acyclic networks is one of the important ways to deeply understand the function of the entire network.The edges of the directed acyclic network constructed by the actual systems usually have different relations: adversary or similarity.Most of the existing community detection algorithms are not suitable for directed acyclic networks of adversarial relations.For directed acyclic networks of similar relations,there are also problems of separation from clustering algorithms and high complexity.Given the above phenomenon,this article explores the community detection in two types of directed acyclic networks,the main research contents and results are as follows:A Katz-Simrank method that can be used to find communities in directed acyclic networks of adversarial relations is proposed.This method uses Katz and Simrank++proximity to capture the order information and similarity information of the nodes respectively and converts the community detection problem in directed acyclic networks into the clique detection problem in weighted undirected networks.In the test of four different types of directed acyclic networks,the NMI,ARI,Homo and Diversity of the community partition obtained by this method are all better than the previous modularitybased method and layering method,verifying this method's superiority.Aiming at directed acyclic networks of similar relations,Katz proximity is used to describe the closeness of the interaction between nodes,which is used as their similarity to improve the Versatile Graph Embeddings from Similarity Measures(FVERSE).Combined with K-means,a community detection framework based on Katz-FVERSE is proposed.After testing on various artificial networks and real networks,it is found that 87.5% of NMI and modularity indicators of community partition obtained by this framework surpassed and approached other optimal frameworks,which proves that it performs better on the task of community detection.The improved Katz-FVERSE-based community detection algorithm framework is applied to an artificial citation network and a real network with different degree distributions,and it is found that there is a significant connection between the node roles closely based on the community structure and node's importance.The Hub nodes most of whose edges are located in the community itself and distribute heterogeneously in each community have 81.4%and 75% of the probability of being important nodes,which is much higher than nodes of other roles and has statistical significance.Therefore,the role of nodes in the network can be judged by community detection to realize the prediction of important nodes.