研究者詳細 - 金子　晋丈

論文 - 金子　晋丈

分割表示 59 件中 1 - 20 件目／全件表示 >>

Local community detection by random walk on hypergraphs

Oka R., Matsumoto N., Takai Y., Ikeda M., Kaneko K.

Communications in Statistics - Theory and Methods （Taylor & Francis） 1 - 20 2025年07月

研究論文（学術雑誌）, 共著, 最終著者, 査読有り, ISSN 03610926

Hypergraphs have been attracting more attention because they are suitable for representing real-world networks with complex relations of three or more terms. Clustering hypergraphs is a fundamental task in network analysis. Although several algorithms for finding a community with a theoretical guarantee are already known, almost all require information on the entire hypergraph for calculation. In this study, we propose a personalized PageRank random walk on a hypergraph and an algorithm for hypergraphs to extract a local community, which can be calculated purely locally. We experimentally show that the algorithm outperforms a benchmark method for real-world hypergraphs. We also evaluate the matching rates with the local community and weak ties using F<inf>1</inf>-scores while varying several parameters for a synthetic hypergraph generated by a stochastic block model.

Access to Document (DOI)

Weighted APPR with restart for community extraction from multilayer networks

Nakano S., Yamashita T., Shin A., Matsumoto N., Kaneko K.

Knowledge and Information Systems （Springer） 1 - 21 2025年06月

研究論文（学術雑誌）, 共著, 最終著者, 査読有り, ISSN 02191377

Community extraction is widely used for various applications concerning network analysis, but its scope has mostly been confined to single-layer network. However, the real-world data are frequently represented as multilayer network, and furthermore, each layer frequently exhibits different properties. It is thus critical to be able to control to what degree each layer should be reflected in the overall network, in order to perform a reliable community extraction. In this paper, we propose a superimposition method called WAPPRS (weighted APPR with restart) that can monotonically increase the degree of reflection and handle a wide range of values for reflection. Our experiments demonstrate that our proposed model outperforms previous models when dealing with the properties desirable for reliable community extraction from multilayer networks.

Access to Document (DOI)

Balancing Global Importance and Source Proximity for Personalized Recommendations Using Random Walk Length

Yamashita T., Kaneko K.

Lecture Notes in Computer Science （Springer） 15669 141 - 153 2025年05月

研究論文（国際会議プロシーディングス）, 最終著者, 査読有り, ISSN 03029743

For personalized recommendation in graphs, random walks starting from the user’s interest node are known as a general-purpose and fast analysis method. Specifically, Personalized PageRank (PPR), which quantifies the importance of each node by the distribution of visited nodes in random walks, determines nodes with high global importance and source proximity. However, it is difficult to balance both influences monotonically. This paper clarifies that the random walks length is effective to monotonically control the balance of both influences on PPR vectors. In particular, we exploit the fact that correlation between PPR and PageRank values monotonically changes depending on PPR parameter that controls the average random walk length. Here, PageRank is a metric that quantifies the global importance by the probability of random walks from all nodes visiting each node. A case study using the movie rating dataset showed that nodes that are considered to be directly related to the source node get high PPR value by shortening the average random walk length. Moreover, statistical evaluation on nine real-world datasets revealed that changing the average random walk length from 1.01 to 100 resulted in a monotonic increase of the cosine similarity between PPR and PageRank vectors from 0.002 to 0.76 at the maximum.

Access to Document (DOI)

Reducing Re-Indexing for Top-k Personalized PageRank Computation on Dynamic Graphs

Yamashita T., Matsumoto N., Kaneko K.

IEEE Transactions on Big Data （IEEE） 11 （ 4 ） 1707 - 1719 2025年01月

研究論文（学術雑誌）, 共著, 最終著者, 査読有り

Top-k Personalized PageRank (PPR) is a graph analysis method used to determine the k most important nodes with respect to a source node. To realize fast Top-k PPR computation, indexing for each node is effective. When we apply the index-based Top-k PPR methods to dynamic graphs, the index becomes stale with edge updates, and index correction is required. Although the existing methods perform index correction for every update to guarantee Top-k PPR accuracy, they involve heavy re-indexing computation or significant memory overhead. This paper proposes a method that achieves comparable accuracy to guaranteed methods while significantly reducing re-indexing by focusing on the fact that index references are concentrated on the nodes whose index is unlikely to change due to edge updates. In particular, our method omits re-indexing as long as we achieve comparable accuracy. Furthermore, our method involves the minimum memory overhead among the existing index-based methods. The space complexity of the index is Θ (n + m), where n and m are the number of nodes and edges of the graph, respectively. The evaluation results using real-world datasets show that our method achieves more than 0.999 Normalized Discounted Cumulative Gain until 20% of edges are updated from index generation.

Access to Document (DOI)

A Flexible Weighting Framework For Converting Relational Database To Hypergraphs

Fujii K., Yamashita T., Shin A., Kaneko K.

International Conference on Information Networking （IEEE Computer Society） 607 - 612 2025年

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 19767684

We propose a framework for converting relational databases (RDB) into hypergraphs to adjust and output various PageRank (PR) correlations by weighting hyperedges and nodes. While analyzing PR of converted graphs can reveal multifaceted information about relationships in the data, conventional methods struggled to balance the correlations between node PR and degree (NPR correlation) and edge PR and shared field records (EPR correlation). Our approach introduces two exponential weighting parameters: α for edge size, influencing EPR correlation, and β for node degree, influencing NPR correlation. By adjusting these parameters, various PR correlations can be obtained. Evaluation using real-world data demonstrate that our model can convert RDBs into hypergraphs with flexibility.

Access to Document (DOI)

Large Language Models Lack Understanding of Character Composition of Words

Shin A., Kaneko K.

Proc. of ICML Workshop on Large Language Models and Cognition abs/2405.11357 1 - 11 2024年07月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り

Large language models (LLMs) have demonstrated remarkable performances on a wide range of natural language tasks. Yet, LLMs' successes have been largely restricted to tasks concerning words, sentences, or documents, and it remains questionable how much they understand the minimal units of text, namely characters. In this paper, we examine contemporary LLMs regarding their ability to understand character composition of words, and show that most of them fail to reliably carry out even the simple tasks that can be handled by humans with perfection. We analyze their behaviors with comparison to token level performances, and discuss the potential directions for future research.

Access to Document (DOI)

Fast Personalized PageRank for Customized Analysis Range Using Static Index

Yamashita T., Kaneko K.

Proc. of the 15th International Conference on Ubiquitous and Future Networks （IEEE） 304 - 309 2024年07月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 21658528

PPR is an essential computation for customized graph analysis, and its fast computation methods have been proposed. FORA +, one of the fastest methods, introduces an index to speed up PPR computation by referencing the end nodes of pre-generated random walks with a specific termination probability αindex. Although for customized graph analysis, it is essential to query with different termination probabilities α for controlling the analysis range, FORA + does not contribute to the speedup for such different α other than the αindex. This paper proposes a method to quickly determine the end nodes of random walks for arbitrary termination probabilities α(≤ αindex) by focusing on the fact that the random walks become probabilistically longer as the termination probability decreases. In particular, we repeatedly reference the index based on the probability p defined by αindex and α to make the longer random walks. By defining p according to mathematical considerations, the results of our method are guaranteed. In addition, our method can be used in FORA + without modifying its index structure. We incorporate our method into FORA + and evaluate the processing time using six real-world graph datasets. As a result, our method achieves up to 19.8 times speedup over the existing index-free method.

Access to Document (DOI)

The Lost Melody: Empirical Observations on Text-to-Video Generation From A Storytelling Perspective.

Shin A., Mori Y., Kaneko K.

Proc. of CVPR 2024 Workshop on AI for Content Creation (AI4CC) abs/2405.08720 1 - 12 2024年05月

研究論文（国際会議プロシーディングス）, 共著, 査読有り

Access to Document (DOI)

Minimum Steiner Tree Approximation for Extracting Unknown Information via Avoiding High-Centrality Nodes

Nishiyama R., Shin A., Matsumoto N., Kaneko K.

Proc. of the 38th International Conference on Information Networking (ICOIN) （IEEE） 2024-January 581 - 586 2024年01月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 19767684

Minimum Steiner tree is frequently used as a means for information retrieval, particularly for search with keyword. While it tends to include high-centrality nodes, the information obtained from such tree may already be accessible to the user, which is not very useful. In this paper, we propose a Steiner tree that avoids high-centrality nodes, in order to increase the likelihood of information being unknown to the user, and thus more useful, while maintaining a high degree of relevance to the keywords. We examine various schemes to select high-centrality nodes to avoid, and compare them in terms of the degree of relevance with the keyword, probability of being unknown to the user, and the pre-computation time. We employ degree centrality and betweenness centrality as our metric for centrality. We find that, our best-performing scheme, despite its simplicity, is able to reduce more than 5% in terms of the number of betweenness centrality nodes compared to the minimum Steiner tree, along with its pre-computation time being about 20% times faster, regardless of our choice of centrality metric.

Access to Document (DOI)

Cache-Efficient Approach for Index-Free Personalized PageRank

Tsuchida K., Matsumoto N., Shin A., Kaneko K.

IEEE Access （IEEE） 11 6944 - 6957 2023年01月

研究論文（学術雑誌）, 共著, 最終著者, 査読有り

Personalized PageRank (PPR) measures the importance of vertices with respect to a source vertex. Since real-world graphs are evolving rapidly, PPR computation methods need to be index-free and fast. Unfortunately, existing index-free methods suffer from cache misses. They follow the state-of-the-art algorithm that first performs the Forward Push (FP) phase and subsequently runs the random walk Monte-Carlo simulation (MC) phase. Although existing methods succeed in reducing cache misses in the FP phase, an inefficient data layout limits their performance improvement. Besides, existing methods have overlooked the importance of reducing cache misses in the MC phase. In this paper, we propose a cache-efficient approach that accelerates both FP and MC phases. In the FP phase, we first reorder the data layout with low overheads. Specifically, we utilize the Breadth First Search result so that vertices near the source vertex are co-located on the reordered data layout. We subsequently perform optimized FP, namely Distance-Extension Forward Push (DEFP). By preferentially proceeding FP around the source vertex, DEFP improves memory access locality. In the MC phase, we perform optimized MC, namely Vertex-Centric Random Walk (VCRW). VCRW aggregates random walks at each vertex to eliminate redundant memory access for repeatedly obtaining neighbor vertices. We prove that most of the random walks can be aggregated while maintaining accuracy guarantees. Experimental results show that the proposed method is up to 4.7x faster than existing index-free methods and outperforms the state-of-the-art index-oriented method under rigorous accuracy guarantees.

Access to Document (DOI)

Node-Centric Random Walk for Fast Index-Free Personalized PageRank

Tsuchida K., Matsumoto N., Kaneko K.

Proc. of International Conference on Information Networking （IEEE） 2023-January 194 - 199 2023年01月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 19767684

Personalized PageRank (PPR) is a popular graph computation in various real-world applications. Since massive real-world graphs are evolving rapidly, PPR computation methods require index-free and fast. In general, index-free methods go through Forward Push phase and random walk Monte-Carlo simulation phase respectively. While existing methods have succeeded in accelerating the Forward Push phase, there is a space for running-time improvements in the second phase that performs a large number of sequential random walks. Through this sequential process, each random walk needs to obtain neighbor nodes for every single step, which causes redundant operation at each node as a result. Our proposal is a node-centric random walk that aggregates random walks at each node and minimizes the total number of obtaining neighbor nodes in the second phase. Most of the random walks can be aggregated while maintaining theoretical guarantees because they do not need to memorize the starting node. In addition, we review the expected running time of random walk Monte-Carlo simulation focusing on the total number of obtaining neighbor nodes. We conducted extensive experiments using four real-world graphs. Experimental results showed that our proposed method is up to 3.3x faster than the existing methods.

Access to Document (DOI)

WalkOrder: Combining Graph Sampling and Reordering for Fast Computation

Tsuchida K., Kaneko K.

Proc. of International Conference on Scientific Computing （American Council on Science & Education） 1 - 13 2022年07月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り

A smaller graph sampled from a large graph uses an excessively wide range of vertex IDs beyond its graph size, which causes a sparse layout on memory. Gorder is a state-of-the-art graph reordering technique for layout optimization. However, despite providing performance improvement, applying Gorder to a sampled graph requires lengthy and impractical time periods,such as reordering time and waiting time for the completion of sampling. In addition, it is unsuitable for multicore graph computation because high and low degree vertices are separated on memory by reordering. We propose WalkOrder, a technique that conducts gradual graph reordering in parallel with sampling; sampling is performed by the widely used Metropolis-Hastings Random Walk. WalkOrder reduces reordering costs of Gorder and balances workload between cores. Our extensive experiments on six real-world graphs revealed that WalkOrder was faster than baseline techniques by an average of 1.52 times and a maximum of 1.95 times.

オープンなデジタルミュージアムー多様な価値の共存と高い規模拡張性

金子　晋丈

デジタルアーカイブ・ベーシックス4 アートシーンを支える（勉誠出版） 203 - 217 2020年11月

論文集(書籍)内論文, 単著, 筆頭著者, 最終著者, 責任著者, 査読有り

Inserting layer-5 to provide applications with richer functions through common API

Watanabe H., Kondo T., Kaneko K., Teraoka F.

IEICE Transactions on Communications （IEICE） E101-B （ 9 ） 1967 - 1981 2018年09月

研究論文（学術雑誌）, 共著, 査読有り, ISSN 09168516

Recently, application demands placed on the network have become more multifaceted. Highly functional application-to-application communication services such as bandwidth aggregation, fault tolerant communication, and delay/disruption tolerant networking (DTN) were developed independently in the network layer, the transport layer, and the application layer. As a result, protocol layering has become complicated. This paper proposes to insert Layer-5 (L5) between the application layer and the transport layer to separate communication policies and communication mechanisms to make protocol layering clearer. The transport layer (L4) provides end-to-end communication mechanisms such as reliable byte stream while L5 realizes communication policies such as bandwidth aggregation by combining the communication mechanisms in L4. This paper proposes five types of L5-paths as communication policies: (1) the L5 bundled path for bandwidth aggregation or fault tolerant communication, (2) the L5 spatially-spliced path for communication with middleboxes, (3) the L5 temporally-spliced path for DTN, (4) the L5 spliced-bundled path, and (5) the L5 bundled over spatially-spliced path. An application can select and use an appropriate L5-path depending on the network circumstances through a common API. A prototype of L5 is implemented in the Linux user space as a library to make deployment and maintenance easier. An evaluation shows that establishment time of L5-paths is short enough and performance of L5-paths is comparable or superior to existing technologies.

Access to Document (DOI)

Activation server for bidirectional limited usages of digital objects

Ogitani R., Kaneko K.

Proceedings IEEE 16th International Conference on Dependable Autonomic and Secure Computing IEEE 16th International Conference on Pervasive Intelligence and Computing IEEE 4th International Conference on Big Data Intelligence and Computing and IEEE 3rd Cyber Science and Technology Congress Dasc Picom Datacom Cyberscitec 2018 （IEEE） 1008 - 1015 2018年08月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り

Limiting data usage is an important issue for data sharing. Big data, in particular, has numerous potential values; thus, an arbitrary value can be extracted as an output by processing data with an arbitrary program. If a data provider simply shares his data with users, the users may get information that the data provider does not want to disclose. However, currently, there is no mechanism to limit the usage of such data. In our approach, a data provider and a program provider specify a combination of data and program files bidirectionally to limit their usages. The Activation Server binds the specified data and program, and then the Activation Server processes the data with the program and sends the output to the user specified by the data provider. We assume that a third-party organization has certified the security for the Activation Server. We implemented and evaluated the Activation Server to demonstrate that it enables data sharing by limiting the usage of digital objects.

Access to Document (DOI)

ZINK: An efficient information centric networking utilizing layered network architecture

Kondo T., Yoshihara S., Kaneko K., Teraoka F.

IEICE Transactions on Communications （IEICE） E101-B （ 8 ） 1853 - 1865 2018年08月

研究論文（学術雑誌）, 共著, 査読有り, ISSN 1745-1345

This paper argues that a layered approach is more suitable for Information CentricNetworking (ICN) than a narrow-waist approach and proposes an ICN mechanism called ZINK. In ZINK, a location-independent content name is resolved to a list of node IDs of content servers in the application layer and a node ID is mapped to a node locator in the network layer, which results in scalable locator-based routing. An ID/Locator split approach in the network layer can efficiently support client/serever mobility. Efficient content transfer is achieved by using sophisticated functions in the transport layer such as multipath transfer for bandwidth aggregation or fault tolerance. Existing well-tuned congestion control in the transport layer achieves fairness not only among ICN flows but also among ICN flows and other flows. A proof-of concept prototype of ZINK is implemented on an IPv6 stack. Evaluation results show that the time for content finding is practical, efficient content transfer is possible by using multipath transfer, and the mobility support mechanism is scalable as shown in a nationwide experiment environment in Japan.

Access to Document (DOI)

Polymorphic cataloguing and interactive 3D visualization for multiple context of digital content: MoSaIC

Ishikawa H., Kaneko K.

Lecture Notes in Computer Science （Springer） 10714 172 - 186 2017年12月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 03029743

In this paper, we propose two methods of interactive visualization of the MoSaIC catalogue. We proposed a conceptual modeling for manifold relationships among digital content files as polymorphic catalogues and its visualization system (MoSaIC-II) before. In the modeling, two structures are provided to express the relationships. One is “grouping objects”. The other is “associating between two objects”. The relationship is constructed by using the combination of two structures, and it is described by using directed graph called a MoSaIC catalogue. Multiple catalogues can be connected by shared objects polymorphically. To visualize the catalogue, we propose two methods which are polymorphic topology view and layer view in MoSaIC system using 3D computer graphics. In the previous method, some objects might be overlapped depending on object connections. Then a lot of objects and complex connection of edges can users feel complicated. Using the new methods, object overlap and the complexity of catalogue and object connections can be improved. In the polymorphic topology view, users can see topology of connected objects avoiding object overlaps. Furthermore, we propose the layer view to show objects aligned by a catalogue creator. In the layer view, users can see connected objects which are aligned and exhibited on each catalogue layer. In this method, a complex connection of edges is improved and comparatively a lot of objects can be handled.

Access to Document (DOI)

Content espresso: A distributed large file sharing system for digital content productions

Ando D., Teraoka F., Kaneko K.

IEICE Transactions on Information and Systems （IEICE） E100-D （ 9 ） 2100 - 2117 2017年09月

研究論文（学術雑誌）, 共著, 最終著者, 査読有り, ISSN 1745-1361

With rapid growth of producing high-resolution digital contents such as Full HD, 4K, and 8K movies, the demand for low cost and high throughput sharing of content files is increasing at digital content productions. In order to meet this demand, we have proposed DRIP (Distributed chunks Retrieval and Integration Procedure), a storage and retrieval mechanism for large file sharing using forward error correction (FEC) and global dispersed storage. DRIP was confirmed that it contributes to low cost and high throughput sharing. This paper describes the design and implementation of Content Espresso, a distributed large file sharing system for digital content productions using DRIP, and presents performance evaluations. We set up experimental environment using 79 physical machines including 72 inexpensive storage servers, and evaluate file metadata access performance, file storage/retrieval performance, FEC block size, and system availability by emulating global environments. The results confirm that Content Espresso has capability to deal with 15,000 requests per second, achieves 1 Gbps for file storage, and achieves more than 3 Gbps for file retrieval. File storage and retrieval performance are not significantly affected by the network conditions. Thus, we conclude that Content Espresso is capable of a global scale file sharing system for digital content productions.

Access to Document (DOI)

PTP accuracy measurement comparison between boundary clock and VLAN priority

Horita K., Shiobara S., Okamawari T., Teraoka F., Kaneko K.

Proc. of 2017 IEEE International Symposium on Precision Clock Synchronization for Measurement, Control, and Communication (ISPCS) （IEEE） 53 - 58 2017年08月

研究論文（国際会議プロシーディングス）, 共著, 最終著者, 査読有り, ISSN 19490305

IEEE1588 (PTP: Precise Time Protocol), which aims for the sub-microsecond range of clock synchronization in a minimal network, is currently focused on highly precise clock synchronization. Boundary Clock (BC) and VLAN Priority are considered to be features that improve PTP accuracy. Although some papers addressed the accuracy, these evaluations were realized using different evaluation metrics and environments. We make them comparable to analyse the contribution of BC and VLAN Priority to precise clock synchronization. Our accuracy evaluation used PTP nodes available on the market and shows the results following the test cases defined in the ITU-T G.8261 Recommendation and IEEE1588 standard. The measurement results show that the accuracy was better than 200 nanoseconds with BC enabled, while it was about one microsecond with BC disabled. We observed that the accuracy was improved to approximately 850 nanoseconds when VLAN Priority was enabled.

Access to Document (DOI)

Separating communication policies and mechanisms to make protocol layering clearer

Watanabe H., Kondo T., Kaneko K., Teraoka F.

Proc. of the 26th International Conference on Computer Communication and Networks (ICCCN 2017) （IEEE） 1 - 9 2017年07月

研究論文（国際会議プロシーディングス）, 共著, 査読有り

Recently, applications' demands for the network become more multifaceted. Highly functional application-to- application communication services such as bandwidth aggregation, fault tolerant communication, and delay/disruption tolerant networking (DTN) were developed independently in the network layer, the transport layer, and the application layer. As a result, protocol layering has become complicated. This paper proposes Layer-5 (L5) inserted between the application layer and the trans- port layer to separate communication policies and communication mechanisms to make protocol layering clearer. The transport layer (L4) provides end-to-end communication mechanisms such as reliable byte stream while L5 realizes communication policies such as bandwidth aggregation by combining the communication mechanisms in L4. This paper proposes five types of L5-paths as communication policies: (1) the L5 bundled path for bandwidth aggregation or fault tolerant communication, (2) the L5 spatially- spliced path for communication with middleboxes, (3) the L5 temporally-spliced path for DTN, (4) the L5 spliced- bundled path, and (5) the L5 bundled over spatially-spliced path. An application can select and use an appropriate L5- path depending on the network circumstances through a common API. A prototype of L5 is implemented in the Linux user space as a library to make deployment and maintenance easier. The evaluation shows that establishment time of L5- paths is short enough and performance of L5-paths is comparable or superior to existing technologies.

Access to Document (DOI)

　前のページ - 次のページ　

金子 晋丈

論文 - 金子 晋丈

金子　晋丈

論文 - 金子　晋丈