{"corpus_id":30057235,"paper_sha":"5c41275be31ae114139541d52b2237a9434ab3b0","doi":"10.1137/1.9781611975055.3","arxiv_id":"1710.01143","pmid":null,"pmcid":null,"mag_id":2949361588,"dblp_id":"books/crc/22/AngrimanBBM22","acl_id":null,"title":"Computing Top-k Closeness Centrality in Fully-dynamic Graphs","year":2017,"publication_date":"2017-10-03","venue":"Workshop on Algorithm Engineering and Experimentation","journal":{"name":"ArXiv","pages":null,"volume":"abs/1710.01143"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":23,"citation_count":23,"influential_citation_count":1,"is_open_access":true,"arxiv_categories":["cs.DS"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://epubs.siam.org/doi/pdf/10.1137/1.9781611975055.3","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/5c41275be31ae114139541d52b2237a9434ab3b0","s2_open_access_license":null,"s2_open_access_status":"BRONZE","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"Closeness is a widely-studied centrality measure. Since it requires all pairwise distances, computing closeness for all nodes is infeasible for large real-world networks. However, for many applications, it is only necessary to find the k most central nodes and not all closeness values. Prior work has shown that computing the top-k nodes with highest closeness can be done much faster than computing closeness for all nodes in real-world networks. However, for networks that evolve over time, no dynamic top-k closeness algorithm exists that improves on static recomputation. In this paper, we present several techniques that allow us to efficiently compute the k nodes with highest (harmonic) closeness after an edge insertion or an edge deletion. Our algorithms use information obtained during earlier computations to omit unnecessary work. However, they do not require asymptotically more memory than the static algorithms (i. e., linear in the number of nodes). We propose separate algorithms for complex networks (which exhibit the small-world property) and networks with large diameter such as street networks, and we compare them against static recomputation on a variety of real-world networks. On many instances, our dynamic algorithms are two orders of magnitude faster than recomputation; on some large graphs, we even reach average speedups between $10^3$ and $10^4$.","claims":[{"public_id":"cl_ef97ed62198d9b4bdd67cad53d64c0ad","status":"active","text":"On many real-world instances, the dynamic algorithms are two orders of magnitude faster than static recomputation, with average speedups between 10^3 and 10^4 on some large graphs.","confidence":0.99,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_ef97ed62198d9b4bdd67cad53d64c0ad"},{"public_id":"cl_28889494398c483d908bb00c33b6d5a0","status":"active","text":"Separate algorithms are proposed for complex networks with the small-world property and for large-diameter networks such as street networks.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_28889494398c483d908bb00c33b6d5a0"},{"public_id":"cl_b90061f6cefa63bf0e2ba78ab5fe74fc","status":"active","text":"Several techniques efficiently compute the k nodes with highest harmonic closeness after an edge insertion or edge deletion.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_b90061f6cefa63bf0e2ba78ab5fe74fc"},{"public_id":"cl_88ca0e1afd495a8cc72357536daa3260","status":"active","text":"The algorithms reuse information from earlier computations to omit unnecessary work without asymptotically exceeding linear memory.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_88ca0e1afd495a8cc72357536daa3260"}],"concepts":[{"public_id":"co_1382991fe528f9aa90bf48213dbdbfa4","status":"active","name":"large-diameter networks","description":"Networks whose shortest-path distances can be relatively large, as contrasted with complex networks.","types":["graph type"],"aliases":["networks with large diameter"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1382991fe528f9aa90bf48213dbdbfa4"},{"public_id":"co_1b934c70c86f8098bf1f8dd34a895b41","status":"active","name":"complex networks","description":"Networks characterized in the abstract as exhibiting the small-world property.","types":["graph type"],"aliases":["small-world networks"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1b934c70c86f8098bf1f8dd34a895b41"},{"public_id":"co_23f205b2fa7d164d70f9314f62260f5b","status":"active","name":"street networks","description":"Road-network graphs used as an example of large-diameter networks.","types":["graph type"],"aliases":["street graph networks"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_23f205b2fa7d164d70f9314f62260f5b"},{"public_id":"co_4fbddaa9d25f90afcf81e78488887920","status":"active","name":"top-k closeness centrality","description":"The task of identifying the k nodes with the highest closeness values in a graph.","types":["graph algorithm task"],"aliases":["top-k closeness"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_4fbddaa9d25f90afcf81e78488887920"},{"public_id":"co_5f86736fd8d9407283280552d1e4b597","status":"active","name":"linear memory","description":"Memory usage that grows proportionally with the number of nodes in the graph.","types":["complexity bound"],"aliases":["linear in the number of nodes"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5f86736fd8d9407283280552d1e4b597"},{"public_id":"co_66f5f8e167197b73de808ac0d8cb7773","status":"active","name":"edge insertion","description":"An update operation that adds an edge to a graph.","types":["graph update"],"aliases":["insertion"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_66f5f8e167197b73de808ac0d8cb7773"},{"public_id":"co_703530a6be2e2bac2ee021b30c6f1025","status":"active","name":"edge deletion","description":"An update operation that removes an edge from a graph.","types":["graph update"],"aliases":["deletion"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_703530a6be2e2bac2ee021b30c6f1025"},{"public_id":"co_7ed99632df212ba68f45c02c4b02afb4","status":"active","name":"earlier computations","description":"Previously computed information reused by the dynamic algorithms to reduce work.","types":["algorithmic state"],"aliases":["prior computations"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_7ed99632df212ba68f45c02c4b02afb4"},{"public_id":"co_81bdd08c0fd315212289f1646f262476","status":"active","name":"small-world property","description":"A network property associated with short paths and high local clustering.","types":["graph property"],"aliases":["small-world"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_81bdd08c0fd315212289f1646f262476"},{"public_id":"co_aedb4c8ceb636cf1fa9e7d688a4d5668","status":"active","name":"speedups","description":"Runtime improvements reported relative to static recomputation.","types":["evaluation metric"],"aliases":["speedup"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_aedb4c8ceb636cf1fa9e7d688a4d5668"},{"public_id":"co_d619db0a93668befea2e3170379c67c6","status":"active","name":"harmonic closeness","description":"A variant of closeness centrality based on the harmonic mean of distances.","types":["centrality measure"],"aliases":["harmonic closeness centrality"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d619db0a93668befea2e3170379c67c6"},{"public_id":"co_e8312f5f2f89ea969474a65de09cb568","status":"active","name":"dynamic algorithms","description":"Algorithms that update their results as the underlying graph changes over time.","types":["algorithm"],"aliases":["fully-dynamic algorithms"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_e8312f5f2f89ea969474a65de09cb568"},{"public_id":"co_fa2c37a4dd993d5b79bc818ddd1ddfad","status":"active","name":"real-world networks","description":"Empirical graph instances used for evaluation.","types":["dataset","evaluation setting"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_fa2c37a4dd993d5b79bc818ddd1ddfad"},{"public_id":"co_fefdef68e6a3a913b20190123b0a106a","status":"active","name":"static recomputation","description":"Recomputing closeness from scratch after each graph update.","types":["baseline","algorithm"],"aliases":["recomputation"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_fefdef68e6a3a913b20190123b0a106a"}],"external_ids":{"DOI":"10.1137/1.9781611975055.3","ArXiv":"1710.01143","PubMed":null,"PubMedCentral":null,"MAG":2949361588,"DBLP":"books/crc/22/AngrimanBBM22","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://epubs.siam.org/doi/pdf/10.1137/1.9781611975055.3","landing_url":"https://www.semanticscholar.org/paper/5c41275be31ae114139541d52b2237a9434ab3b0","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":null,"status":"BRONZE","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":638489,"paper_uid":"beedfe94-c612-4663-8027-c9d5b0854b5a","canonical_identity":{"paper_id":638489,"paper_uid":"beedfe94-c612-4663-8027-c9d5b0854b5a","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/30057235"}