Search

Abstract Hypergraph is a graph structure that can efficiently express the relationship of multiple nodes and has attracted attention in recent years. As with normal graphs, the structure changes every moment, and it is an important research topic in graph mining to capture structural changes. Many existing graph embedding methods focus on prediction tasks, and few focus on the visualization of structural changes. In this study, we aim to output embeddings for effective visualization in terms of spatial efficiency, node classification accuracy, graph structure maintenance, computational efficiency, and structural change detection performance. Our proposed method gets inspired by modularity maximization, quantifies connection strength between hypernodes and hyperedges, and embeds hypernodes on the surface of concentric spheres with a radius equal to the timestep, where a spherical surface has a wide area in the middle range. These devices are expected to correspond to the following two characteristics: (1) a graph has more node pairs whose distances are middle-range than short- and long-range; (2) a growing graph generally has an increasing number of nodes. Evaluation experiments using multiple real hypergraphs show that the proposed method is superior to existing visualization methods in the abovementioned terms.

Abstract This study tackles the problem of extracting the node roles in uncertain graphs based on network motifs. Uncertain graphs are useful for modeling information diffusion phenomena because the presence or absence of edges is stochastically determined. In such an uncertain graph, the node role also changes stochastically according to the presence or absence of edges, so approximate calculation using a huge number of samplings is common. However, the calculation load is very large, even for a small graph. We propose a method to extract uncertain node roles with high accuracy and high speed by ensembling a large number of sampled graphs and efficiently searching for all other transitionable roles. This method provides highly accurate results compared to simple sampling and ensembling methods that do not consider the transition to other roles. In our evaluation experiment, we use real-world graphs artificially assigned uniform and non-uniform edge existence probabilities. The results show that the proposed method outperforms an existing method previously reported by the authors, which is the basis of the proposed method, as well as another current method based on the state-of-the-art algorithm, in terms of efficiency and accuracy.

Abstract In this study, we propose novel centrality measures considering multiple perspectives of nodes or node groups based on the facility location problem on a spatial network. The conventional centrality exclusively quantifies the global properties of each node in a network such as closeness and betweenness, and extracts nodes with high scores as important nodes. In the context of facility placement on a network, it is desirable to place facilities at nodes with high accessibility from residents, that is, nodes with a high score in closeness centrality. It is natural to think that such a property of a node changes when the situation changes. For example, in a situation where there are no existing facilities, it is expected that the demand of residents will be satisfied by opening a new facility at the node with the highest accessibility, however, in a situation where there exist some facilities, it is necessary to open a new facility some distance from the existing facilities. Furthermore, it is natural to consider that the concept of closeness differs depending on the relationship with existing facilities, cooperative relationships and competitive relationships. Therefore, we extend a concept of centrality so as to considers the situation where one or more nodes have already been selected belonging to one of some groups. In this study, we propose two measures based on closeness centrality and betweenness centrality as behavior models of people on a spatial network. From our experimental evaluations using actual urban street network data, we confirm that the proposed method, which introduces the viewpoints of each group, shows that there is a difference in the important nodes of each group viewpoint, and that the new store location can be predicted more accurately.

Abstract Many networks including spatial networks, social networks, and web networks, are not deterministic but probabilistic due to the uncertainty of link existence. From networks with such uncertainty, to extract densely connected nodes, we propose connectedness centrality and its extended version, group connectedness centrality, where the connectedness of each node is defined as the expected size of its connected component over all possible graphs produced by an uncertain graph. In a large-scale network, however, since the number of combinations of possible graphs is enormous, it is difficult to strictly calculate the expected value. Therefore, we also propose an efficient estimation method based on Monte Carlo sampling. When applying our method to road networks, the extracted nodes can be regarded as candidate sites of evacuation facilities that many residents can reach even in the situation where roads are stochastically blocked by natural disasters. In our experimental evaluations using actual road networks, we show the following promising characteristics: our proposed method 1) works stably with respect to the number of simulations; 2) extracts nodes set reachable from more nodes even in a situation that many links are deleted; and 3) computes much more efficient, compared to existing centrality measures and community extraction methods.

Abstract Dividing a geographical region into some subregions with common characteristics is an important research topic, and has been studied in many research fields such as urban planning and transportation planning. In this paper, by network analysis approach, we attempt to extract functionally similar regions, each of which consists of functionally similar nodes of a road network. For this purpose, we previously proposed the Functional Cluster Extraction method, which takes a large amount of computation time to output clustering results because it treats too many high-dimensional vectors. To overcome this difficulty, we also previously proposed a transfer learning-based clustering method that selects approximate medoids from the target network using the K medoids of a previously clustered network and divides all the nodes into K clusters. If we select an appropriate network with similar structural characteristics, this method produces highly accurate clustering results. However it is difficult to preliminarily know which network is appropriate. In this paper, we extend this method to ensure accuracy using the K medoids of multiple networks rather than a specific network. Using actual urban streets, we evaluate our proposed method from the viewpoint of the improvement degree of clustering accuracy and computation time.