Centrality

Who is more important in a network? Who controls the flow between nodes?

The betweenness and closeness metrics are widely used metrics in many network analysis applications. Yet, they are expensive to compute. For that reason, making the betweenness and closeness centrality computations faster is an important and well-studied problem.

Closeness centrality is defined as:

\[far(u) = \sum_{v \in V, d(u,v)} d(u,v) \ \ \ \ cc[u] = \frac{1}{far(u)}\]

Betweenness centrality is defined as:

\[bc(u) = \sum_{s\neq u \neq t \in V} \frac{\sigma_{st}(u)}{\sigma_{st}}\]

We developed efficient parallel algorithms and vectorization techniques for centrality computations. We proposed also proposed BADIOS framework which manipulates the graph by compressing it and splitting into pieces so that the centrality computation can be handled independently for each piece.

A sample iteration of BADIOS framework.

Related Publications

  1. JRNL
    Graph Manipulations for Fast Centrality Computation
    Ahmet Erdem Sarıyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek
    ACM Transactions on Knowledge Discovery from Data, 2017.
  2. JRNL
    Incremental Closeness Centrality in Distributed Memory
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    Parallel Computing, 2015.
  3. JRNL
    Regularizing Graph Centrality Computations
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    Journal of Parallel and Distributed Computing, 2015.
  4. Misc
    Computing the Closeness Centrality of Evolving Networks on Clusters
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    Poster, SIAM Workshop on Network Science (NS14), 2014.
  5. Conf
    Hardware/Software Vectorization for Closeness Centrality on Multi-/Many-Core Architectures
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    In 28th International Parallel and Distributed Processing Symposium Workshops, Workshop on Multithreaded Architectures and Applications (MTAAP), 2014.
  6. Conf
    Incremental Algorithms for Closeness Centrality
    Ahmet Erdem Sarıyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek
    In Proc of IEEE Int’l Conference on BigData, 2013.
  7. Conf
    STREAMER: a Distributed Framework for Incremental Closeness Centrality Computation
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    In Proc. of IEEE Cluster 2013, 2013.
  8. Conf
    Shattering and Compressing Networks for Betweenness centrality
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    In SIAM International Conference on Data Mining (SDM), 2013, An extended version is available on ArXiv.
  9. Conf
    Betweenness Centrality on GPUs and Heterogeneous Architectures
    Ahmet Erdem Sarıyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek
    In Workshop on General Purpose Processing Using GPUs (GPGPU), in conjunction with ASPLOS, 2013.
  10. Tech
    Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
    Ahmet Erdem Sarıyüce, Kamer Kaya, Erik Saule, and Ümit V. Çatalyürek
    ArXiv arXiv:1303.0422, 2013.
  11. Tech
    Shattering and Compressing Networks for Centrality Analysis
    Ahmet Erdem Sarıyüce, Erik Saule, Kamer Kaya, and Ümit V. Çatalyürek
    ArXiv arXiv:1209.6007, 2012.