Search

Predicting the connections or interactions between nodes in networks remains a fundamental task in network analysis. In target systems, nodes with different types are connected with each other through different relations, as in typical heterogeneous networks. Link prediction can help identify implied information in heterogeneous target operational network (HTON) to boost network reconstruction. In view of the complex network structure of target systems and diversified types of edges alongside the low accuracy and poor interpretability issues of previous methods, we proposed an HTON reconstruction framework (HTONRP) incorporating rule-based reasoning and meta-path-based link prediction. To start with, the link rules are extracted based on operational doctrine, military theory, system formulation, etc., and then they are reasoned with initial nodes and relations (input) and the inferred target relations (output) to improve the target systems architecture. Afterwards, the data are input into the meta-path-based link prediction model of HTON, through which the architecture of target systems is further perfected. The experiments are carried out on real data instances of HTON and results suggest that the proposed method can effectively improve the prediction performance and enhance model interpretability compared to traditional baselines.

A large class of decision and optimization problems can be defined as finding a connected sub graph in a graph while satisfying certain requirements. This paper studies the Unbalanced Connected Subgraphs problem, referred to as UBCS problem. Given a graph with nodes belonging to different categories, the objective of UBCS problem is to find the maximum connected subgraph in which the number and proportion of nodes in certain categories can meet given requirements, respectively. This problem has many real-world applications, for example, to find the largest subgraph of a social network in which the proportion of people who likes a specific product is not less than a given value. This paper introduces the formal definition of UBCS problem, studies its computational complexity and proves that it is NP-hard in planar graphs. A mixed integer programming model based on network flow is proposed to formulate this problem. Moreover, a simple and fast heuristic algorithm is designed to solve UBCS problem in large-scale sparse graphs. Through numerical experiments, the advantages and disadvantages of the heuristic are verified and compared with the optimization solver IBM ILOG CPLXE.

In the Extended Flexible Job Shop Scheduling Problem (EFJSP), the temporal constraints among the tasks could be very complex including serial, parallel and flexible relations. This paper presents a method for identifying the critical tasks that affect the makespan most remarkably, which we call the "bottleneck tasks". To this end, we first transfer the solution of the EFJSP, which corresponds to a schedule plan, into an AOE Network (Activity On Edge Network), and then propose a bottleneck identification index based on the critical paths of the AOE Network. The tasks with the biggest bottleneck identification index value are identified as bottleneck tasks. The experimental results show that the bottleneck identification index as well as its computing method proposed in this paper are effective for identifying critical tasks. Moreover, it is proved that the time complexity of the bottleneck identification method is O((NJ * NT)^2), where NJ denotes the number of jobs and NT denotes the number of tasks in each job, respectively.

The heterogeneous information networks are omnipresent in real-world applications, which consist of multiple types of objects with various rich semantic meaningful links among them. Community discovery is an effective method to extract the hidden structures in networks. Usually, heterogeneous information networks are time-evolving, whose objects and links are dynamic and varying gradually. In such time-evolving heterogeneous information networks, community discovery is a challenging topic and quite more difficult than that in traditional static homogeneous information networks. In contrast to communities in traditional approaches, which only contain one type of objects and links, communities in heterogeneous information networks contain multiple types of dynamic objects and links. Recently, some studies focus on dynamic heterogeneous information networks and achieve some satisfactory results. However, they assume that heterogeneous information networks usually follow some simple schemas, such as bityped network and star network schema. In this paper, we propose a multityped community discovery method for time-evolving heterogeneous information networks with general network schemas. A tensor decomposition framework, which integrates tensor CP factorization with a temporal evolution regularization term, is designed to model the multityped communities and address their evolution. Experimental results on both synthetic and real-world datasets demonstrate the efficiency of our framework.

Community discovery in a dynamic heterogeneous information network is a challenging topic and quite more difficult than that in a traditional static homogeneous information network. Community in heterogeneous information network, named multi-typed community, contains multiple types of dynamic objects and links, which brings three challenges. Firstly, the multi-typed communities are heterogeneous. Secondly, The communities are constantly changing along time. Finally, the network schemas for different heterogeneous information networks are various. To overcome these challenges, we propose a multi-typed community discovery method for dynamic heterogeneous information networks through tensor method without the restriction of network schema. A tensor decomposition framework is designed to model the multi-typed community and address the community evolution. Experimental result on a real-world dataset demonstrates the efficiency of our framework.

Predicting missing links in networks plays a significant role in modern science. On the basis of structural similarity, our paper proposes a new node-similarity-based measure called biased resource allocation (BRA), which is motivated by the resource allocation (RA) measure. Comparisons between BRA and nine well-known node-similarity-based measures on five real networks indicate that BRA performs no worse than RA, which was the best node-similarity-based index in previous researches. Afterwards, based on localPath (LP) and Katz measure, we propose another two improved measures, named Im-LocalPath and Im-Katz respectively. Numerical results show that the prediction accuracy of both Im-LP and Im-Katz measure improve compared with the original LP and Katz measure. Finally, a new path-similarity-based measure and its improved measure, called LYU and Im-LYU measure, are proposed and especially, Im-LYU measure is shown to perform more remarkably than other mentioned measures.