Digital Library[ Search Result ]
Cascading Behavior and Information Diffusion in Overlapping Clusters
Woojung Lee, Joyce Jiyoung Whang
http://doi.org/10.5626/JOK.2020.47.4.422
Information diffusion models formulate and explain cascading behavior in networks where a small set of initial adopters is assumed to acquire new information and the new information is propagated to the other nodes in the network. Most existing information diffusion models assume that a node in a network belongs to only one cluster, and based on this assumption, it has been shown that clusters are obstacles to cascades. However, in many real-world networks, a node can belong to multiple clusters, i.e., clusters can overlap. In this paper, we study cascading behavior in a network when clusters overlap. We show that clusters are not obstacles to cascades if the initial adopters are placed in the overlapped region between the clusters or if we allow compatibility. We verify our theorems and models on four real-world datasets.
Graph Convolutional Networks with Elaborate Neighborhood Selection
Yeonsung Jung, Joyce Jiyoung Whang
http://doi.org/10.5626/JOK.2019.46.11.1193
Graph Convolutional Networks (GCNs) utilize the convolutional structure to obtain an effective insight on representation by aggregating the information from neighborhoods. In order to demonstrate high performance, it is necessary to select neighborhoods that can propagate important information to target nodes, and acquire appropriate filter values during training. Recent GCNs algorithms adopt simple neighborhood selection methods, such as taking all 1-hop nodes. In the present case, unnecessary information was propagated to the target node, resulting in degradation of the performance of the model. In this paper, we propose a GCN algorithm that utilizes valid neighborhoods by calculating the similarity between the target node and neighborhoods.
A Distributed Vertex Rearrangement Algorithm for Compressing and Mining Big Graphs
Namyong Park, Chiwan Park, U Kang
How can we effectively compress big graphs composed of billions of edges? By concentrating non-zeros in the adjacency matrix through vertex rearrangement, we can compress big graphs more efficiently. Also, we can boost the performance of several graph mining algorithms such as PageRank. SlashBurn is a state-of-the-art vertex rearrangement method. It processes real-world graphs effectively by utilizing the power-law characteristic of the real-world networks. However, the original SlashBurn algorithm displays a noticeable slowdown for large-scale graphs, and cannot be used at all when graphs are too large to fit in a single machine since it is designed to run on a single machine. In this paper, we propose a distributed SlashBurn algorithm to overcome these limitations. Distributed SlashBurn processes big graphs much faster than the original SlashBurn algorithm does. In addition, it scales up well by performing the large-scale vertex rearrangement process in a distributed fashion. In our experiments using real-world big graphs, the proposed distributed SlashBurn algorithm was found to run more than 45 times faster than the single machine counterpart, and process graphs that are 16 times bigger compared to the original method.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr