The Experts below are selected from a list of 4761 Experts worldwide ranked by ideXlab platform

Kwang-hoon Kim - One of the best experts on this subject based on the ideXlab platform.

  • An Estimated Closeness Centrality Ranking Algorithm and Its Performance Analysis in Large-Scale Workflow-supported Social Networks
    Ksii Transactions on Internet and Information Systems, 2016
    Co-Authors: Jawon Kim, Hyun Ahn, Minjae Park, Sangguen Kim, Kwang-hoon Kim
    Abstract:

    This paper implements an estimated ranking algorithm of Closeness Centrality measures in large-scale workflow-supported social networks. The traditional ranking algorithms for large-scale networks have suffered from the time complexity problem. The larger the network size is, the bigger dramatically the computation time becomes. To solve the problem on calculating ranks of Closeness Centrality measures in a large-scale workflow-supported social network, this paper takes an estimation-driven ranking approach, in which the ranking algorithm calculates the estimated Closeness Centrality measures by applying the approximation method, and then pick out a candidate set of top k actors based on their ranks of the estimated Closeness Centrality measures. Ultimately, the exact ranking result of the candidate set is obtained by the pure Closeness Centrality algorithm [1] computing the exact Closeness Centrality measures. The ranking algorithm of the estimation-driven ranking approach especially developed for workflow-supported social networks is named as RankCCWSSN (Rank Closeness Centrality Workflow-supported Social Network) algorithm. Based upon the algorithm, we conduct the performance evaluations, and compare the outcomes with the results from the pure algorithm. Additionally we extend the algorithm so as to be applied into weighted workflow-supported social networks that are represented by weighted matrices. After all, we confirmed that the time efficiency of the estimation-driven approach with our ranking algorithm is much higher (about 50% improvement) than the traditional approach.

  • An Estimated Closeness Centrality Ranking Algorithm for Large-Scale Workflow Affiliation Networks
    Journal of Internet Computing and Services, 2016
    Co-Authors: Do-kyong Lee, Hyun Ahn, Kwang-hoon Kim
    Abstract:

    A type of workflow affiliation network is one of the specialized social network types, which represents the associative relation between actors and activities. There are many methods on a workflow affiliation network measuring centralities such as degree Centrality, Closeness Centrality, betweenness Centrality, eigenvector Centrality. In particular, we are interested in the Closeness Centrality measurements on a workflow affiliation network discovered from enterprise workflow models, and we know that the time complexity problem is raised according to increasing the size of the workflow affiliation network. This paper proposes an estimated ranking algorithm and analyzes the accuracy and average computation time of the proposed algorithm. As a result, we show that the accuracy improves 47.5%, 29.44% in the sizes of network and the rates of samples, respectively. Also the estimated ranking algorithm`s average computation time improves more than 82.40%, comparison with the original algorithm, when the network size is 2400, sampling rate is 30%.

  • performance analysis of an estimated Closeness Centrality ranking algorithm in large scale workflow supported social networks
    Journal of Internet Computing and Services, 2015
    Co-Authors: Jawon Kim, Hyun Ahn, Kwang-hoon Kim
    Abstract:

    This paper implements an estimated Closeness Centrality ranking algorithm in large-scale workflow-supported social networks and performance analyzes of the algorithm. Existing algorithm has a time complexity problem which is increasing performance time by network size. This problem also causes ranking process in large -scale workflow-supported social networks. To solve such problems, this paper conducts comparison analysis on the existing algorithm and estimated results by applying estimated-driven RankCCWSSN(Rank Closeness Centrality Workflow-supported Social Network). The RankCCWSSN algorithm proved its time-efficiency in a procedure about 50% decrease.

  • Implementing Closeness Centrality measurements on workflow-supported enterprise social networks
    2015 17th International Conference on Advanced Communication Technology (ICACT), 2015
    Co-Authors: Hyun Ahn, Haksung Kim, Minjae Park, Kwang-hoon Kim
    Abstract:

    The purpose of this paper is to implement the theoretical Closeness Centrality measurement algorithm [1] that was proposed by the authors' research group in order to numerically analyze Closeness Centrality measures among workflow-performers on a workflow-supported social network model. We implement the essential part of the proposed algorithm[l], which is a Closeness Centrality analysis equation. Finally, we illustrate the implemented algorithm by showing its run-time screen-shots with an operational example.

  • A Closeness Centrality Analysis Algorithm for Workflow-supported Social Networks
    Journal of Korean Society for Internet Information, 2013
    Co-Authors: Sungjoo Park, Kwang-hoon Kim
    Abstract:

    This paper proposes a Closeness Centrality analysis algorithm for workflow-supported social networks that represent the collaborative relationships among the performers who are involved in a specific workflow model. The proposed algorithm uses the social network analysis techniques, particularly Closeness Centrality equations, to analyze the Closeness Centrality of the workflow-supported social network. Additionally, through an example we try to verify the accuracy and appropriateness of the proposed algorithm.

Claudio Gutierrez - One of the best experts on this subject based on the ideXlab platform.

Ümit V. Çatalyürek - One of the best experts on this subject based on the ideXlab platform.

  • Incremental Closeness Centrality in distributed memory
    Parallel Computing, 2015
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    We propose a distributed memory framework for incremental Closeness Centrality computation.We parallelize different components of the framework for faster solution.Vectorization is applied to make the computation faster.All the algorithms and techniques are experimentally validated.Our framework proves to be practical for real time scenarios. Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness Centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the Closeness Centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the Closeness Centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster.

  • hardware software vectorization for Closeness Centrality on multi many core architectures
    International Parallel and Distributed Processing Symposium, 2014
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Centrality metrics have shown to be highly correlated with the importance and loads of the nodes in a network. Given the scale of today's social networks, it is essential to use efficient algorithms and high performance computing techniques for their fast computation. In this work, we exploit hardware and software vectorization in combination with finegrain parallelization to compute the Closeness Centrality values. The proposed vectorization approach enables us to do concurrent breadth-first search operations and significantly increases the performance. We provide a comparison of different vectorization schemes and experimentally evaluate our contributions with respect to the existing parallel CPU-based solutions on cutting-edge hardware. Our implementations achieve to be 11 times faster than the state-of-the-art implementation for a graph with 234 million edges. The proposed techniques are beneficial to show how the vectorization can be efficiently utilized to execute other graph kernels that require multiple traversals over a large-scale network on cutting-edge architectures.

  • IPDPS Workshops - Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core Architectures
    2014 IEEE International Parallel & Distributed Processing Symposium Workshops, 2014
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Centrality metrics have shown to be highly correlated with the importance and loads of the nodes in a network. Given the scale of today's social networks, it is essential to use efficient algorithms and high performance computing techniques for their fast computation. In this work, we exploit hardware and software vectorization in combination with finegrain parallelization to compute the Closeness Centrality values. The proposed vectorization approach enables us to do concurrent breadth-first search operations and significantly increases the performance. We provide a comparison of different vectorization schemes and experimentally evaluate our contributions with respect to the existing parallel CPU-based solutions on cutting-edge hardware. Our implementations achieve to be 11 times faster than the state-of-the-art implementation for a graph with 234 million edges. The proposed techniques are beneficial to show how the vectorization can be efficiently utilized to execute other graph kernels that require multiple traversals over a large-scale network on cutting-edge architectures.

  • streamer a distributed framework for incremental Closeness Centrality computation
    International Conference on Cluster Computing, 2013
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Networks are commonly used to model the traffic patterns, social interactions, or web pages. The nodes in a network do not possess the same characteristics: some nodes are naturally more connected and some nodes can be more important. Closeness Centrality (CC) is a global metric that quantifies how important is a given node in the network. When the network is dynamic and keeps changing, the relative importance of the nodes also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the Closeness Centrality scores of a network upon changes. It leverages pipelined and replicated parallelism and takes NUMA effects into account. It speeds up the maintenance of the CC of a real graph with 916K vertices and 4.3M edges by a factor of 497 using a 64 nodes cluster.

  • Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
    arXiv: Data Structures and Algorithms, 2013
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Analyzing networks requires complex algorithms to extract meaningful information. Centrality metrics have shown to be correlated with the importance and loads of the nodes in network traffic. Here, we are interested in the problem of Centrality-based network management. The problem has many applications such as verifying the robustness of the networks and controlling or improving the entity dissemination. It can be defined as finding a small set of topological network modifications which yield a desired Closeness Centrality configuration. As a fundamental building block to tackle that problem, we propose incremental algorithms which efficiently update the Closeness Centrality values upon changes in network topology, i.e., edge insertions and deletions. Our algorithms are proven to be efficient on many real-life networks, especially on small-world networks, which have a small diameter and a spike-shaped shortest distance distribution. In addition to Closeness Centrality, they can also be a great arsenal for the shortest-path-based management and analysis of the networks. We experimentally validate the efficiency of our algorithms on large networks and show that they update the Closeness Centrality values of the temporal DBLP-coauthorship network of 1.2 million users 460 times faster than it would take to compute them from scratch. To the best of our knowledge, this is the first work which can yield practical large-scale network management based on Closeness Centrality values.

Ricardo Mora - One of the best experts on this subject based on the ideXlab platform.

Ahmet Erdem Sariyuce - One of the best experts on this subject based on the ideXlab platform.

  • Incremental Closeness Centrality in distributed memory
    Parallel Computing, 2015
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    We propose a distributed memory framework for incremental Closeness Centrality computation.We parallelize different components of the framework for faster solution.Vectorization is applied to make the computation faster.All the algorithms and techniques are experimentally validated.Our framework proves to be practical for real time scenarios. Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness Centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the Closeness Centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the Closeness Centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster.

  • hardware software vectorization for Closeness Centrality on multi many core architectures
    International Parallel and Distributed Processing Symposium, 2014
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Centrality metrics have shown to be highly correlated with the importance and loads of the nodes in a network. Given the scale of today's social networks, it is essential to use efficient algorithms and high performance computing techniques for their fast computation. In this work, we exploit hardware and software vectorization in combination with finegrain parallelization to compute the Closeness Centrality values. The proposed vectorization approach enables us to do concurrent breadth-first search operations and significantly increases the performance. We provide a comparison of different vectorization schemes and experimentally evaluate our contributions with respect to the existing parallel CPU-based solutions on cutting-edge hardware. Our implementations achieve to be 11 times faster than the state-of-the-art implementation for a graph with 234 million edges. The proposed techniques are beneficial to show how the vectorization can be efficiently utilized to execute other graph kernels that require multiple traversals over a large-scale network on cutting-edge architectures.

  • IPDPS Workshops - Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core Architectures
    2014 IEEE International Parallel & Distributed Processing Symposium Workshops, 2014
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Centrality metrics have shown to be highly correlated with the importance and loads of the nodes in a network. Given the scale of today's social networks, it is essential to use efficient algorithms and high performance computing techniques for their fast computation. In this work, we exploit hardware and software vectorization in combination with finegrain parallelization to compute the Closeness Centrality values. The proposed vectorization approach enables us to do concurrent breadth-first search operations and significantly increases the performance. We provide a comparison of different vectorization schemes and experimentally evaluate our contributions with respect to the existing parallel CPU-based solutions on cutting-edge hardware. Our implementations achieve to be 11 times faster than the state-of-the-art implementation for a graph with 234 million edges. The proposed techniques are beneficial to show how the vectorization can be efficiently utilized to execute other graph kernels that require multiple traversals over a large-scale network on cutting-edge architectures.

  • streamer a distributed framework for incremental Closeness Centrality computation
    International Conference on Cluster Computing, 2013
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Networks are commonly used to model the traffic patterns, social interactions, or web pages. The nodes in a network do not possess the same characteristics: some nodes are naturally more connected and some nodes can be more important. Closeness Centrality (CC) is a global metric that quantifies how important is a given node in the network. When the network is dynamic and keeps changing, the relative importance of the nodes also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the Closeness Centrality scores of a network upon changes. It leverages pipelined and replicated parallelism and takes NUMA effects into account. It speeds up the maintenance of the CC of a real graph with 916K vertices and 4.3M edges by a factor of 497 using a 64 nodes cluster.

  • Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
    arXiv: Data Structures and Algorithms, 2013
    Co-Authors: Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, Ümit V. Çatalyürek
    Abstract:

    Analyzing networks requires complex algorithms to extract meaningful information. Centrality metrics have shown to be correlated with the importance and loads of the nodes in network traffic. Here, we are interested in the problem of Centrality-based network management. The problem has many applications such as verifying the robustness of the networks and controlling or improving the entity dissemination. It can be defined as finding a small set of topological network modifications which yield a desired Closeness Centrality configuration. As a fundamental building block to tackle that problem, we propose incremental algorithms which efficiently update the Closeness Centrality values upon changes in network topology, i.e., edge insertions and deletions. Our algorithms are proven to be efficient on many real-life networks, especially on small-world networks, which have a small diameter and a spike-shaped shortest distance distribution. In addition to Closeness Centrality, they can also be a great arsenal for the shortest-path-based management and analysis of the networks. We experimentally validate the efficiency of our algorithms on large networks and show that they update the Closeness Centrality values of the temporal DBLP-coauthorship network of 1.2 million users 460 times faster than it would take to compute them from scratch. To the best of our knowledge, this is the first work which can yield practical large-scale network management based on Closeness Centrality values.