Link prediction finds the future or the missing links in a social–biological complex network such as a friendship network, citation network, or protein network. Current methods to link prediction follow the network properties, such as the node’s centrality, the number of edges, or the weights of the edges, among many others. As the properties of the networks vary, the link prediction methods also vary. These methods are inaccurate since they exploit limited information. This work presents a link prediction method based on the stochastic block model. The novelty of our approach is the three-step process to find the most-influential nodes using the m-PageRank metric, forming blocks using the global clustering coefficient and, finally, predicting the most-optimized links using maximum likelihood estimation. Through the experimental analysis of social, ecological, and biological datasets, we proved that the proposed model outperforms the existing state-of-the-art approaches to link prediction.
26 March 2024 in Information and Software Technology
Complex Networks can depict a clear image of real-world systems. A real-world scenario can be represented a graph with interconnected layers - called a multi-layer network. Finding motifs can give an idea of the topology of complex systems and helps to understand the dynamics in the graphs. Looking at motifs as atoms of the network is helpful to analyze the relationship between nodes, and between layers. In this work, we suggest a sub-graph enumeration approach to find and count the motifs in multi-layer network. The proposed work has many application in graph mining, particularly to structure and dynamics of complex networks.
We propose a summarization technique that provides a clear and concise picture of the history of program execution with respect to entities of interest to a programmer. We develop our technique in the context of JIVE, a tool for Java execution visualization that renders execution states and history using UML object and sequence diagrams respectively. While these notations have been developed for specifying design-time decisions, the distinguishing aspect of our work is that we adapt their use for execution-time. Sequence diagrams tend to be long and unwieldy, and often exhibit a repetitive structure, hence we develop a novel procedure to summarize the sequence diagram in the form a state diagram with finite states. This summarization is user-driven, in that the user annotates the key variables of interest in the source code. This information together with an execution trace of the program for a particular input enables us to systematically construct a state diagram that summarizes the program behavior for that input. Using multiple execution traces, we show how an integrated state summarization can be obtained. Finally, by choosing different sets of variables, the user may view different summarizations, or perspectives, of the execution. This paper presents our technique along with experimental results from summarizing several different program executions in order to illustrate the benefit of our approach.
We present a novel framework for formal verification of run-time behaviour of Java programs. We focus on the class of programs with a repetitive behaviour, such as servers and interactive programs, including programs exhibiting concurrency and non-determinism. The design-time specifications for such programs can be specified as UML-like finite-state diagrams, or Kripke structures, in the terminology of model checking. In order to verify the run-time behavior of a Java program, we extract a state diagram from the execution trace of the Java program and check whether the run-time state diagram is consistent with the design-time diagram. We have implemented this framework as an extension of JIVE (Java Interactive Visualization Environment), a state-of-the-art dynamic analysis and visualization tool which constructs object, sequence, and state diagrams for Java program executions. JIVE is available as an open-source plugin for Eclipse and makes available the execution trace for facilitating analyses of program executions. We have tested our extension on a number of programs, and our experiments show that our methodology is effective in helping close the gap between the design and implementation of Java programs.