Optimal search strategies on complex multi-linked networks.
Ontology highlight
ABSTRACT:
SUBMITTER: Di Patti F
PROVIDER: S-EPMC4423499 | biostudies-literature | 2015 May
REPOSITORIES: biostudies-literature
Publications
Optimal search strategies on complex multi-linked networks.
Di Patti Francesca F Fanelli Duccio D Piazza Francesco F
Scientific reports 20150507
In this paper we consider the problem of optimal search strategies on multi-linked networks, i.e. graphs whose nodes are endowed with several independent sets of links. We focus preliminarily on agents randomly hopping along the links of a graph, with the additional possibility of performing non-local hops to randomly chosen nodes with a given probability. We show that an optimal combination of the two jump rules exists that maximises the efficiency of target search, the optimum reflecting the t ...[more]
Similar Datasets
Project description:To develop optimal search strategies in Medline for retrieving systematic reviews.Analytical survey.161 journals published in 2000 indexed in Medline.The sensitivity, specificity, and precision of retrieval of systematic reviews of 4862 unique terms in 782,485 combinations of one to five terms were determined by comparison with a hand search of all articles (the criterion standard) in 161 journals published during 2000 (49,028 articles).Only 753 (1.5%) of the 49,028 articles were systematic reviews. The most sensitive strategy included five terms and had a sensitivity of 99.9% (95% confidence interval 99.6% to 100%) and a specificity of 52% (51.6% to 52.5%). The strategy that best minimised the difference between sensitivity and specificity had a sensitivity of 98% (97% to 99%) and specificity of 90.8% (90.5% to 91.1%). Highest precision for multiterm strategies, 57% (54% to 60%), was achieved at a sensitivity of 71% (68% to 74%). The term "cochrane database of systematic reviews.jn." was the most precise single term search strategy (sensitivity of 56% (52% to 60%) and precision of 96% (94% to 98%)). These strategies are available through the "limit" screen of Ovid's search interface for Medline.Systematic reviews can be retrieved from Medline with close to perfect sensitivity or specificity, or with high precision, by using empirical search strategies.
| S-EPMC543864 | biostudies-other
Project description:BackgroundEvidence from health services research (HSR) is currently thinly spread through many journals, making it difficult for health services researchers, managers and policy-makers to find research on clinical practice guidelines and the appropriateness, process, outcomes, cost and economics of health care services. We undertook to develop and test search terms to retrieve from the MEDLINE database HSR articles meeting minimum quality standards.MethodsThe retrieval performance of 7445 methodologic search terms and phrases in MEDLINE (the test) were compared with a hand search of the literature (the gold standard) for each issue of 68 journal titles for the year 2000 (a total of 25,936 articles). We determined sensitivity, specificity and precision (the positive predictive value) of the MEDLINE search strategies.ResultsA majority of the articles that were classified as outcome assessment, but fewer than half of those in the other categories, were considered methodologically acceptable (no methodologic criteria were applied for cost studies). Combining individual search terms to maximize sensitivity, while keeping specificity at 50% or more, led to sensitivities in the range of 88.1% to 100% for several categories (specificities ranged from 52.9% to 97.4%). When terms were combined to maximize specificity while keeping sensitivity at 50% or more, specificities of 88.8% to 99.8% were achieved. When terms were combined to maximize sensitivity and specificity while minimizing the differences between the 2 measurements, most strategies for HSR categories achieved sensitivity and specificity of at least 80%.InterpretationSensitive and specific search strategies were validated for retrieval of HSR literature from MEDLINE. These strategies have been made available for public use by the US National Library of Medicine at www.nlm.nih.gov/nichsr/hedges/search.html.
| S-EPMC524948 | biostudies-literature
Project description:Many complex systems experience damage accumulation, which leads to aging, manifest as an increasing probability of system collapse with time. This naturally raises the question of how to maximize health and longevity in an aging system at minimal cost of maintenance and intervention. Here, we pose this question in the context of a simple interdependent network model of aging in complex systems and show that it exhibits cascading failures. We then use both optimal control theory and reinforcement learning alongside a combination of analysis and simulation to determine optimal maintenance protocols. These protocols may motivate the rational design of strategies for promoting longevity in aging complex systems with potential applications in therapeutic schedules and engineered system maintenance.
| S-EPMC7456090 | biostudies-literature
Project description:Locating sources of diffusion and spreading from minimum data is a significant problem in network science with great applied values to the society. However, a general theoretical framework dealing with optimal source localization is lacking. Combining the controllability theory for complex networks and compressive sensing, we develop a framework with high efficiency and robustness for optimal source localization in arbitrary weighted networks with arbitrary distribution of sources. We offer a minimum output analysis to quantify the source locatability through a minimal number of messenger nodes that produce sufficient measurement for fully locating the sources. When the minimum messenger nodes are discerned, the problem of optimal source localization becomes one of sparse signal reconstruction, which can be solved using compressive sensing. Application of our framework to model and empirical networks demonstrates that sources in homogeneous and denser networks are more readily to be located. A surprising finding is that, for a connected undirected network with random link weights and weak noise, a single messenger node is sufficient for locating any number of sources. The framework deepens our understanding of the network source localization problem and offers efficient tools with broad applications.
| S-EPMC5414272 | biostudies-literature
Project description:Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.
| S-EPMC2786939 | biostudies-literature
Project description:ObjectiveTo develop optimal search strategies in Medline for retrieving sound clinical studies on the diagnosis of health disorders.DesignAnalytical survey.SettingMedline, 2000.Participants170 journals for 2000 of which 161 were indexed in Medline.Main outcome measuresThe sensitivity, specificity, precision ("positive predictive value"), and accuracy of 4862 unique terms in 17,287 combinations were determined by comparison with a hand search of all articles (the "gold standard") in 161 journals published during 2000 (49,028 articles).ResultsOnly 147 (18.9%) of 778 articles about diagnostic tests met basic criteria for scientific merit. Combinations of search terms reached peak sensitivities of 98.6% at a specificity of 74.3%. Compared with best single terms, best multiple terms increased sensitivity for sound studies by 6.8% (absolute increase), while also increasing specificity (absolute increase 6.0%) when sensitivity was maximised. When terms were combined to maximise specificity, the single term, specificity.tw. (98.4%), outperformed combinations of terms. The strategies newly reported in this paper outperformed other validated search strategies except for one strategy that had slightly higher sensitivity (99.3% v 98.6%) but lower specificity (54.7% v 74.3%).ConclusionNew empirical search strategies in Medline can optimise retrieval of articles reporting high quality clinical studies of diagnosis.
| S-EPMC403841 | biostudies-literature
Project description:Recently it has been shown that the control energy required to control a dynamical complex network is prohibitively large when there are only a few control inputs. Most methods to reduce the control energy have focused on where, in the network, to place additional control inputs. Here, in contrast, we show that by controlling the states of a subset of the nodes of a network, rather than the state of every node, while holding the number of control signals constant, the required energy to control a portion of the network can be reduced substantially. The energy requirements exponentially decay with the number of target nodes, suggesting that large networks can be controlled by a relatively small number of inputs as long as the target set is appropriately sized. We validate our conclusions in model and real networks to arrive at an energy scaling law to better design control objectives regardless of system size, energy restrictions, state restrictions, input node choices and target node choices.
| S-EPMC5413984 | biostudies-literature
Project description:Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speed up network data collection and improve network model validation. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 550 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity using network-based metalearning to construct a series of "stacked" models that combine predictors into a single algorithm. Applied to a broad range of synthetic networks, for which we may analytically calculate optimal performance, these stacked models achieve optimal or nearly optimal levels of accuracy. Applied to real-world networks, stacked models are superior, but their accuracy varies strongly by domain, suggesting that link prediction may be fundamentally easier in social networks than in biological or technological networks. These results indicate that the state of the art for link prediction comes from combining individual algorithms, which can achieve nearly optimal predictions. We close with a brief discussion of limitations and opportunities for further improvements.
| S-EPMC7519231 | biostudies-literature
Project description:Health institutions may choose to screen newly admitted patients for the presence of disease in order to reduce disease prevalence within the institution. Screening is costly, and institutions must judiciously choose which patients they wish to screen based on the dynamics of disease transmission. Since potentially infected patients move between different health institutions, the screening and treatment decisions of one institution will affect the optimal decisions of others; an institution might choose to "free-ride" off the screening and treatment decisions of neighboring institutions. We develop a theoretical model of the strategic decision problem facing a health care institution choosing to screen newly admitted patients. The model incorporates an SIS compartmental model of disease transmission into a game theoretic model of strategic decision-making. Using this setup, we are able to analyze how optimal screening is influenced by disease parameters, such as the efficacy of treatment, the disease recovery rate and the movement of patients. We find that the optimal screening level is lower for diseases that have more effective treatments. Our model also allows us to analyze how the optimal screening level varies with the number of decision makers involved in the screening process. We show that when institutions are more autonomous in selecting whom to screen, they will choose to screen at a lower rate than when screening decisions are more centralized. Results also suggest that centralized screening decisions have a greater impact on disease prevalence when the availability or efficacy of treatment is low. Our model provides insight into the factors one should consider when choosing whether to set a mandated screening policy. We find that screening mandates set at a centralized level (i.e. state or national) will have a greater impact on the control of infectious disease.
| S-EPMC3879151 | biostudies-literature
Project description:Countries and cities are likely to enter economic activities that are related to those that are already present in them. Yet, while these path dependencies are universally acknowledged, we lack an understanding of the diversification strategies that can optimally balance the development of related and unrelated activities. Here, we develop algorithms to identify the activities that are optimal to target at each time step. We find that the strategies that minimize the total time needed to diversify an economy target highly connected activities during a narrow and specific time window. We compare the strategies suggested by our model with the strategies followed by countries in the diversification of their exports and research activities, finding that countries follow strategies that are close to the ones suggested by the model. These findings add to our understanding of economic diversification and also to our general understanding of diffusion in networks.
| S-EPMC5889401 | biostudies-literature