China
Africa
Explore chapters and articles related to this topic
Graph Edit Distance—Theory, Algorithms, and Applications
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
The basic idea behind the graph edit distance is to define a dissimilarity measure between two graphs by the minimum amount of distortion required to transform one graph into the other [69, 70, 71, 72]. To this end, a number of distortions or edit operations ed, consisting of the insertion, deletion, and substitution (replacement of a label by another one) of both nodes and edges are defined. Then, for every pair of graphs, G1 and G2, there exists a sequence of edit operations, or edit path ∂(G1,G2)=(ed1,…,edk) (where each edi denotes an edit operation), that transform one graph into the other. In Figure 13.3, an example of an edit path between two given graphs G1 and G2 is shown. In this example, the edit path consists of one edge deletion, one node substitution, one node insertion, and two edge insertions.
Study State Dynamics of Team Passing Networks in Soccer Games
Published in Journal of Sports Sciences, 2023
How much does one team passing network differentiate from another in topology? This is the critical question for distinguishing those static team passing networks and clustering them into various team states. Graph distance measures, which capture the dissimilarities concerning the whole topological structure between two networks instead of only partial features (e.g., clustering coefficient), can be an appropriate tool for this task (Pincombe, 2005; Livi & Rizzi, 2013; De Domenico & Biamonte, 2016; Koutra et al., 2016; Wills & Meyer, 2020). Distinct measures are based on diverse criteria; for instance, the prominent graph edit distance is defined as the minimum total number of edits (e.g., adding/deleting edges between nodes) required to transform one network to another (Gao et al., 2010; Pincombe, 2005). The spectral distance evaluates the disparity between the eigenvalues of the associated matrices which define the networks. Masuda and Holme (2019) compared seven state-of-the-art graph distance measures and concluded that normalized spectral distance and unnormalized spectral distance were two appropriate measures for detecting system states in dynamical networks, which are also applicable for studying team passing networks. Consequently, this work adopted the normalized spectral distance as one of the distance measures to differentiate the team passing networks.
Business process recommendation method based on cost constraints
Published in Connection Science, 2022
Qianqian Wang, Chifeng Shao, Xianwen Fang, Huamin Zhang
Most of the structural similarity measurement methods convert business processes into graphs or trees to calculate edit distance and measure the similarity between processes. Dijkman et al. (2009) used graph edit distance to measure the similarity between two processes, i.e. the minimum cost required to transform one graph into another, but cannot distinguish parallel relationships. Zhou et al. (2019) first constructed weighted business process graph, and then used the weighted graph edit distance to measure business process similarity, which can distinguish parallel relationships. Jia et al. (2012) measured the similarity by the tree edit distance between the two trees. Automata can be represented as directed graphs, and Wombacher and Rozie (2006) analysed the structural similarity of workflows from the perspective of automata. Bae et al. (2007) gave the concept of a process dependency graph and transformed this graph into a process matrix to measure the distance between processes.
Assessment of supervised machine learning algorithms using dynamic API calls for malware detection
Published in International Journal of Computers and Applications, 2022
Vasilescu et al. [16] used Cuckoo sandbox to capture the runtime features which consists of log entries, portable execution information, and API calls. Then malware classifier was trained to detect the zero-day malware. Elhadi et al. [17] proposed the malware detection technique using the graph of API calls. The nodes of the graph represent different API calls along with required system resources. The author used enhanced graph edit distance algorithm which is based on a greedy approach to reduce the matching complexity. Ghiasi et al. [18] extracted API calls using the dynamic analysis by running malware samples into a controlled environment. In this proposed technique, four machine learning algorithms: J48, SMO (Sequential Minimal Optimization) Logistic Regression and Random Forest were applied over the API calls to train the classifiers. The proposed technique was implemented using 850-malware and 300 benign samples which showed the 95.9% accuracy in malware classification. Pirscoveanu et al. [19] run the binary samples using the Cuckoo sandbox and windows’ API calls were stored. They trained the random classifier with 42,000 malware samples which were collected from VirusShare and VxHeaven. The authors claimed the 98% accuracy results. Ki et al. [20] proposed a technique on the basis of the API calls sequence. The order of API call execution was utilized to increase the accuracy results. To handle the irrelevant API calls, the authors used the sequence alignment algorithm. An experiment was done using 23048 malware files and produced 98% true positive rate.