Distributed Identification of Central Nodes with Less Communication
Bibliographic record
Abstract
Abstract This paper is concerned with distributed detection of central nodes in complex networks using closeness centrality. Closeness centrality plays an essential role in network analysis. Distributed tasks such as leader election can make effective use of centrality information for highly central nodes, but complete network information is not locally available. Evaluating closeness centrality exactly requires complete knowledge of the network; for large networks, this may be inefficient, so closeness centrality should be approximated. Here, situations for decentralised network view construction where a node has zero knowledge about other nodes on the network at initial and there is no central node to coordinate evaluations of node closeness centrality are considered. Unlike centralized methods for detection of central nodes, in decentralized methods an approximated view of the network must be available at each node, then each node can evaluate its own closeness centrality before it can share it with others when applicable. Based on our knowledge, there is no much work done under this setting where the leading approach consists of running the breadth-first search Skiena (1998) on each node with a limited number of iterations (which is less than the diameter of the graph into consideration), as done by You et al. (2017), Wehmuth and Ziviani (2012), before each node evaluates its centrality. Running the breadth-first search on each node in a decentralized fashion requires high cost in terms of communication. Our contribution is to consider a better way of constructing network view in a decentralised manner with less communication cost. This paper refines a distributed centrality computation algorithm by You et al. (2017) by pruning nodes which are almost certainly not most central. For example, in a large network, leave nodes can not play a central role. This leads to a reduction in the number of messages exchanged to determine the centrality of the remaining nodes. Our results show that our approach reduces the number of messages for networks which contain many prunable nodes. Our results also show that reducing the number of messages may have a positive impact on running time and memory size.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.003 | 0.012 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.001 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.003 |
| Open science | 0.003 | 0.004 |
| Research integrity | 0.002 | 0.002 |
| Insufficient payload (model declined to judge) | 0.003 | 0.001 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".