Title: Dynamic Laplace: Efficient Centrality Measure for Weighted or Unweighted Evolving Networks,
Abstract: With its origin in sociology, Social Network Analysis (SNA), quickly emerged
and spread to other areas of research, including anthropology, biology,
information science, organizational studies, political science, and computer
science. Being it's objective the investigation of social structures through
the use of networks and graph theory, Social Network Analysis is, nowadays, an
important research area in several domains. Social Network Analysis cope with
different problems namely network metrics, models, visualization and
information spreading, each one with several approaches, methods and
algorithms. One of the critical areas of Social Network Analysis involves the
calculation of different centrality measures (i.e.: the most important vertices
within a graph). Today, the challenge is how to do this fast and efficiently,
as many increasingly larger datasets are available. Recently, the need to apply
such centrality algorithms to non static networks (i.e.: networks that evolve
over time) is also a new challenge. Incremental and dynamic versions of
centrality measures are starting to emerge (betweenness, closeness, etc). Our
contribution is the proposal of two incremental versions of the Laplacian
Centrality measure, that can be applied not only to large graphs but also to,
weighted or unweighted, dynamically changing networks. The experimental
evaluation was performed with several tests in different types of evolving
networks, incremental or fully dynamic. Results have shown that our incremental
versions of the algorithm can calculate node centralities in large networks,
faster and efficiently than the corresponding batch version in both incremental
and full dynamic network setups.