Pour voir les autres types de publications sur ce sujet consultez le lien suivant : Small world graph.
Articles de revues sur le sujet « Small world graph »
Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres
Consultez les 50 meilleurs articles de revues pour votre recherche sur le sujet « Small world graph ».
À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.
Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.
Parcourez les articles de revues sur diverses disciplines et organisez correctement votre bibliographie.
1
Cont, Rama, et Emily Tanimura. « Small-world graphs : characterization and alternative constructions ». Advances in Applied Probability 40, no 4 (décembre 2008) : 939–65. http://dx.doi.org/10.1239/aap/1231340159.
Texte intégralRésumé :
Small-world graphs are examples of random graphs which mimic empirically observed features of social networks. We propose an intrinsic definition of small-world graphs, based on a probabilistic formulation of scaling properties of the graph, which does not rely on any particular construction. Our definition is shown to encompass existing models of small-world graphs, proposed by Watts (1999) and studied by Barbour and Reinert (2001), which are based on random perturbations of a regular lattice. We also propose alternative constructions of small-world graphs which are not based on lattices and study their scaling properties.
2
Cont, Rama, et Emily Tanimura. « Small-world graphs : characterization and alternative constructions ». Advances in Applied Probability 40, no 04 (décembre 2008) : 939–65. http://dx.doi.org/10.1017/s0001867800002913.
Texte intégralRésumé :
Small-world graphs are examples of random graphs which mimic empirically observed features of social networks. We propose an intrinsic definition of small-world graphs, based on a probabilistic formulation of scaling properties of the graph, which does not rely on any particular construction. Our definition is shown to encompass existing models of small-world graphs, proposed by Watts (1999) and studied by Barbour and Reinert (2001), which are based on random perturbations of a regular lattice. We also propose alternative constructions of small-world graphs which are not based on lattices and study their scaling properties.
3
Wong, Pak Chung, Harlan Foote, Patrick Mackey, George Chin, Heidi Sofia et Jim Thomas. « A Dynamic Multiscale Magnifying Tool for Exploring Large Sparse Graphs ». Information Visualization 7, no 2 (17 avril 2008) : 105–17. http://dx.doi.org/10.1057/palgrave.ivs.9500177.
Texte intégralRésumé :
We present an information visualization tool, known as GreenMax, to visually explore large small-world graphs with up to a million graph nodes on a desktop computer. A major motivation for scanning a small-world graph in such a dynamic fashion is the demanding goal of identifying not just the well-known features but also the unknown–known and unknown–unknown features of the graph. GreenMax uses a highly effective multilevel graph drawing approach to pre-process a large graph by generating a hierarchy of increasingly coarse layouts that later support the dynamic zooming of the graph. This paper describes the graph visualization challenges, elaborates our solution, and evaluates the contributions of GreenMax in the larger context of visual analytics on large small-world graphs. We report the results of two case studies using GreenMax and the results support our claim that we can use GreenMax to locate unexpected features or structures behind a graph.
4
Bassett, Danielle S., et Edward T. Bullmore. « Small-World Brain Networks Revisited ». Neuroscientist 23, no 5 (21 septembre 2016) : 499–516. http://dx.doi.org/10.1177/1073858416667720.
Texte intégralRésumé :
It is nearly 20 years since the concept of a small-world network was first quantitatively defined, by a combination of high clustering and short path length; and about 10 years since this metric of complex network topology began to be widely applied to analysis of neuroimaging and other neuroscience data as part of the rapid growth of the new field of connectomics. Here, we review briefly the foundational concepts of graph theoretical estimation and generation of small-world networks. We take stock of some of the key developments in the field in the past decade and we consider in some detail the implications of recent studies using high-resolution tract-tracing methods to map the anatomical networks of the macaque and the mouse. In doing so, we draw attention to the important methodological distinction between topological analysis of binary or unweighted graphs, which have provided a popular but simple approach to brain network analysis in the past, and the topology of weighted graphs, which retain more biologically relevant information and are more appropriate to the increasingly sophisticated data on brain connectivity emerging from contemporary tract-tracing and other imaging studies. We conclude by highlighting some possible future trends in the further development of weighted small-worldness as part of a deeper and broader understanding of the topology and the functional value of the strong and weak links between areas of mammalian cortex.
5
Acharjee, Santanu, Bijit Bora et Robin I. M. Dunbar. « On M-Polynomials of Dunbar Graphs in Social Networks ». Symmetry 12, no 6 (3 juin 2020) : 932. http://dx.doi.org/10.3390/sym12060932.
Texte intégralRésumé :
Topological indices describe mathematical invariants of molecules in mathematical chemistry. M-polynomials of chemical graph theory have freedom about the nature of molecular graphs and they play a role as another topological invariant. Social networks can be both cyclic and acyclic in nature. We develop a novel application of M-polynomials, the ( m , n , r ) -agent recruitment graph where n > 1 , to study the relationship between the Dunbar graphs of social networks and the small-world phenomenon. We show that the small-world effects are only possible if everyone uses the full range of their network when selecting steps in the small-world chain. Topological indices may provide valuable insights into the structure and dynamics of social network graphs because they incorporate an important element of the dynamical transitivity of such graphs.
6
Roux, Jérôme, Nicolas Bez, Paul Rochet, Rocío Joo et Stéphanie Mahévas. « Graphlet correlation distance to compare small graphs ». PLOS ONE 18, no 2 (15 février 2023) : e0281646. http://dx.doi.org/10.1371/journal.pone.0281646.
Texte intégralRésumé :
Graph models are standard for representing mutual relationships between sets of entities. Often, graphs deal with a large number of entities with a small number of connections (e.g. social media relationships, infectious disease spread). The distances or similarities between such large graphs are known to be well established by the Graphlet Correlation Distance (GCD). This paper deals with small graphs (with potentially high densities of connections) that have been somewhat neglected in the literature but that concern important fora like sociology, ecology and fisheries, to mention some examples. First, based on numerical experiments, we study the conditions under which Erdős-Rényi, Fitness Scale-Free, Watts-Strogatz small-world and geometric graphs can be distinguished by a specific GCD measure based on 11 orbits, the GCD11. This is done with respect to the density and the order (i.e. the number of nodes) of the graphs when comparing graphs with the same and different orders. Second, we develop a randomization statistical test based on the GCD11 to compare empirical graphs to the four possible null models used in this analysis and apply it to a fishing case study where graphs represent pairwise proximity between fishing vessels. The statistical test rules out independent pairing within the fleet studied which is a standard assumption in fisheries. It also illustrates the difficulty to identify similarities between real-world small graphs and graph models.
7
Liao, Yunhua, Yaoping Hou et Xiaoling Shen. « Tutte polynomial of a small-world Farey graph ». EPL (Europhysics Letters) 104, no 3 (1 novembre 2013) : 38001. http://dx.doi.org/10.1209/0295-5075/104/38001.
Texte intégral
8
Li, Jonathan, Rohan Potru et Farhad Shahrokhi. « A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph ». Algorithms 13, no 12 (14 décembre 2020) : 339. http://dx.doi.org/10.3390/a13120339.
Texte intégralRésumé :
We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. Over the range of test data, all algorithms perform better than anticipated in theory, and have small performance ratios, measured as the size of output divided by the LP objective lower bound. However, each have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 s of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.
9
Zhang, Lixia, et Jianliang Gao. « Incremental Graph Pattern Matching Algorithm for Big Graph Data ». Scientific Programming 2018 (2018) : 1–8. http://dx.doi.org/10.1155/2018/6749561.
Texte intégralRésumé :
Graph pattern matching is widely used in big data applications. However, real-world graphs are usually huge and dynamic. A small change in the data graph or pattern graph could cause serious computing cost. Incremental graph matching algorithms can avoid recomputing on the whole graph and reduce the computing cost when the data graph or the pattern graph is updated. The existing incremental algorithm PGC_IncGPM can effectively reduce matching time when no more than half edges of the pattern graph are updated. However, as the number of changed edges increases, the improvement of PGC_IncGPM gradually decreases. To solve this problem, an improved algorithm iDeltaP_IncGPM is developed in this paper. For multiple insertions (resp., deletions) on pattern graphs, iDeltaP_IncGPM determines the nodes’ matching state detection sequence and processes them together. Experimental results show that iDeltaP_IncGPM has higher efficiency and wider application range than PGC_IncGPM.
10
Ganesh, Ayalvadi, et Feng Xue. « On the connectivity and diameter of small-world networks ». Advances in Applied Probability 39, no 4 (décembre 2007) : 853–63. http://dx.doi.org/10.1239/aap/1198177228.
Texte intégralRésumé :
We consider two different models of small-world graphs on nodes whose locations are modelled by a stochastic point process. In the first model each node is connected to a fixed number of its nearest neighbours, while in the second model each node is connected to all nodes located within some fixed distance. In both models, nodes are additionally connected via shortcuts to other nodes chosen uniformly at random. We obtain sufficient conditions for connectivity in the first model, and necessary conditions in the second model. Thereby, we show that connectivity is achieved at a smaller value of total degree (nearest neighbours plus shortcuts) in the first model. We also obtain bounds on the diameter of the graph in this model.
11
Ganesh, Ayalvadi, et Feng Xue. « On the connectivity and diameter of small-world networks ». Advances in Applied Probability 39, no 04 (décembre 2007) : 853–63. http://dx.doi.org/10.1017/s0001867800002123.
Texte intégralRésumé :
We consider two different models of small-world graphs on nodes whose locations are modelled by a stochastic point process. In the first model each node is connected to a fixed number of its nearest neighbours, while in the second model each node is connected to all nodes located within some fixed distance. In both models, nodes are additionally connected via shortcuts to other nodes chosen uniformly at random. We obtain sufficient conditions for connectivity in the first model, and necessary conditions in the second model. Thereby, we show that connectivity is achieved at a smaller value of total degree (nearest neighbours plus shortcuts) in the first model. We also obtain bounds on the diameter of the graph in this model.
12
Zhang, Zhongzhi, Bin Wu et Yuan Lin. « Counting spanning trees in a small-world Farey graph ». Physica A : Statistical Mechanics and its Applications 391, no 11 (juin 2012) : 3342–49. http://dx.doi.org/10.1016/j.physa.2012.01.039.
Texte intégral
13
Duchon, Philippe, Nicolas Hanusse, Emmanuelle Lebhar et Nicolas Schabanel. « Could any graph be turned into a small-world ? » Theoretical Computer Science 355, no 1 (avril 2006) : 96–103. http://dx.doi.org/10.1016/j.tcs.2005.12.008.
Texte intégral
14
Cai, Dali, Yilin Hou, Chenxi Zhang, Ning Wang, Zhaohui Chen, Wenlong Song, Zhao Jia, Yao Wang, Weizhong Qian et Fei Wei. « Analyzing transfer properties of zeolites using small-world networks ». Nanoscale 10, no 35 (2018) : 16431–33. http://dx.doi.org/10.1039/c8nr04652b.
Texte intégral
15
Shang, Yilun. « Isoperimetric Numbers of Randomly Perturbed Intersection Graphs ». Symmetry 11, no 4 (1 avril 2019) : 452. http://dx.doi.org/10.3390/sym11040452.
Texte intégralRésumé :
Social networks describe social interactions between people, which are often modeled by intersection graphs. In this paper, we propose an intersection graph model that is induced by adding a sparse random bipartite graph to a given bipartite graph. Under some mild conditions, we show that the vertex–isoperimetric number and the edge–isoperimetric number of the randomly perturbed intersection graph on n vertices are Ω ( 1 / ln n ) asymptomatically almost surely. Numerical simulations for small graphs extracted from two real-world social networks, namely, the board interlocking network and the scientific collaboration network, were performed. It was revealed that the effect of increasing isoperimetric numbers (i.e., expansion properties) on randomly perturbed intersection graphs is presumably independent of the order of the network.
16
Hallquist, Michael N., et Frank G. Hillary. « Graph theory approaches to functional network organization in brain disorders : A critique for a brave new small-world ». Network Neuroscience 3, no 1 (janvier 2019) : 1–26. http://dx.doi.org/10.1162/netn_a_00054.
Texte intégralRésumé :
Over the past two decades, resting-state functional connectivity (RSFC) methods have provided new insights into the network organization of the human brain. Studies of brain disorders such as Alzheimer’s disease or depression have adapted tools from graph theory to characterize differences between healthy and patient populations. Here, we conducted a review of clinical network neuroscience, summarizing methodological details from 106 RSFC studies. Although this approach is prevalent and promising, our review identified four challenges. First, the composition of networks varied remarkably in terms of region parcellation and edge definition, which are fundamental to graph analyses. Second, many studies equated the number of connections across graphs, but this is conceptually problematic in clinical populations and may induce spurious group differences. Third, few graph metrics were reported in common, precluding meta-analyses. Fourth, some studies tested hypotheses at one level of the graph without a clear neurobiological rationale or considering how findings at one level (e.g., global topology) are contextualized by another (e.g., modular structure). Based on these themes, we conducted network simulations to demonstrate the impact of specific methodological decisions on case-control comparisons. Finally, we offer suggestions for promoting convergence across clinical studies in order to facilitate progress in this important field.
17
Chen, Rui, Jianping Li et Weihua He. « Assessing Graph Robustness through Modified Zagreb Index ». Axioms 11, no 9 (19 septembre 2022) : 484. http://dx.doi.org/10.3390/axioms11090484.
Texte intégralRésumé :
Graph robustness or network robustness is the ability that a graph or a network preserves its connectivity or other properties after the loss of vertices and edges, which has been a central problem in the research of complex networks. In this paper, we introduce the Modified Zagreb index and Modified Zagreb index centrality as novel measures to study graph robustness. We theoretically find some relationships between these novel measures and some other graph measures. Then, we use Modified Zagreb index centrality to analyze the robustness of BA scale-free networks, ER random graphs and WS small world networks under deliberate or random vertex attacks. We also study the correlations between this new measure and some other existed measures. Finally, we use Modified Zagreb index centrality to study the robustness of two real world networks. All these results demonstrate the efficiency of Modified Zagreb index centrality for assessing the graph robustness.
18
WU, ZHENGPING, et RENMING WANG. « DISTANCE PREFERENCES SMALL-WORLD COMMUNICATION TOPOLOGY FOR AGENT NETWORK ». International Journal of Modern Physics B 24, no 11 (30 avril 2010) : 1489–99. http://dx.doi.org/10.1142/s0217979210054361.
Texte intégralRésumé :
In multi-agent system (MAS), the communication topology of agent network plays a very important role in its collaboration. Small-world networks are the networks with high local clustering and small average path length, and the communication networks of MAS can be analyzed within the frame of small-world topology. Yet the real multiagent communication networks are abundant and the classical WS small-world model is not suitable for all cases. In this paper, two new small-world network models are presented. One is based on random graph substrate and local nodes preference reconnection and the other is based on regular graph substrate and long-range nodes preference reconnection. The characteristic of the network parameter such as the clustering coefficients, average path length, and eigenvalue λ2 and λn of the Laplacian matrix for these two models and WS model is studied. The consensus problem that based on these three models is also studied. An example is given and the conclusions are made in the end.
19
Yao, Huaxiu, Chuxu Zhang, Ying Wei, Meng Jiang, Suhang Wang, Junzhou Huang, Nitesh Chawla et Zhenhui Li. « Graph Few-Shot Learning via Knowledge Transfer ». Proceedings of the AAAI Conference on Artificial Intelligence 34, no 04 (3 avril 2020) : 6656–63. http://dx.doi.org/10.1609/aaai.v34i04.6142.
Texte intégralRésumé :
Towards the challenging problem of semi-supervised node classification, there have been extensive studies. As a frontier, Graph Neural Networks (GNNs) have aroused great interest recently, which update the representation of each node by aggregating information of its neighbors. However, most GNNs have shallow layers with a limited receptive field and may not achieve satisfactory performance especially when the number of labeled nodes is quite small. To address this challenge, we innovatively propose a graph few-shot learning (GFL) algorithm that incorporates prior knowledge learned from auxiliary graphs to improve classification accuracy on the target graph. Specifically, a transferable metric space characterized by a node embedding and a graph-specific prototype embedding function is shared between auxiliary graphs and the target, facilitating the transfer of structural knowledge. Extensive experiments and ablation studies on four real-world graph datasets demonstrate the effectiveness of our proposed model and the contribution of each component.
20
SHARMA, ROHAN, BIBHAS ADHIKARI et TYLL KRUEGER. « SELF-ORGANIZED CORONA GRAPHS : A DETERMINISTIC COMPLEX NETWORK MODEL WITH HIERARCHICAL STRUCTURE ». Advances in Complex Systems 22, no 06 (septembre 2019) : 1950019. http://dx.doi.org/10.1142/s021952591950019x.
Texte intégralRésumé :
In this paper, we propose a self-organization mechanism for newly appeared nodes during the formation of corona graphs that define a hierarchical pattern in the resulting corona graphs and we call it self-organized corona graphs (SoCG). We show that the degree distribution of SoCG follows power-law in its tail with power-law exponent approximately 2. We also show that the diameter is less equal to 4 for SoCG defined by any seed graph and for certain seed graphs, the diameter remains constant during its formation. We derive lower bounds of clustering coefficients of SoCG defined by certain seed graphs. Thus, the proposed SoCG can be considered as a growing network generative model which is defined by using the corona graphs and a self-organization process such that the resulting graphs are scale-free small-world highly clustered growing networks. The SoCG defined by a seed graph can also be considered as a network with a desired motif which is the seed graph itself.
21
Firsov, A. B., et I. I. Titov. « Small world of the miRNA science drives its publication dynamics ». Vavilov Journal of Genetics and Breeding 26, no 8 (5 janvier 2023) : 826–29. http://dx.doi.org/10.18699/vjgb-22-100.
Texte intégralRésumé :
Many scientific articles became available in the digital form which allows for querying articles data, and specifically the automated metadata gathering, which includes the affiliation data. This in turn can be used in the quantitative characterization of the scientific field, such as organizations identification, and analysis of the co-authorship graph of those organizations to extract the underlying structure of science. In our work, we focus on the miRNA science field, building the organization co-authorship network to provide the higher-level analysis of scientific community evolution rather than analyzing author-level characteristics. To tackle the problem of the institution name writing variability, we proposed the k-mer/n-gram boolean feature vector sorting algorithm, KOFER in short. This approach utilizes the fact that the contents of the affiliation are rather consistent for the same organization, and to account for writing errors and other organization name variations within the affiliation metadata field, it converts the organization mention within the affiliation to the K-Mer (n-gram) Boolean presence vector. Those vectors for all affiliations in the dataset are further lexicographically sorted, forming groups of organization mentions. With that approach, we clustered the miRNA field affiliation dataset and extracted unique organization names, which allowed us to build the co-authorship graph on the organization level. Using this graph, we show that the growth of the miRNA field is governed by the small-world architecture of the scientific institution network and experiences power-law growth with exponent 2.64 ± 0.23 for organization number, in accordance with network diameter, proposing the growth model for emerging scientific fields. The first miRNA publication rate of an organization interacting with already publishing organization is estimated as 0.184 ± 0.002 year–1.
22
Lima, Max, Leonardo Guimarães, Eulanda Santos, Edleno Moura, Rafael Costa, Marco Levorato et Horácio Oliveira. « A Small World Graph Approach for an Efficient Indoor Positioning System ». Sensors 21, no 15 (23 juillet 2021) : 5013. http://dx.doi.org/10.3390/s21155013.
Texte intégralRésumé :
The main goal of an Indoor Positioning System (IPS) is to estimate the position of mobile devices in indoor environments. For this purpose, the primary source of information is the signal strength of packets received by a set of routers. The fingerprint technique is one of the most used techniques for IPSs. By using supervised machine learning techniques, it trains a model with the received signal intensity information so it can be used to estimate the positions of the devices later in an online phase. Although the k-Nearest Neighbors (kNN) is one of the most widely used classification methods due to its accuracy, it has no scalability since a sample that needs to be classified must be compared to all other samples in the training database. In this work, we use a novel hierarchical navigable small world graph technique to build a search structure so the location of a sample can be efficiently found, allowing the IPSs to be used in large-scale scenarios or run on devices with limited resources. To carry out our performance evaluation, we proposed a synthetic IPS dataset generator as well as implemented a complete real-world, large-scale IPS testbed. We compared the performance of our graph-based solution with other known kNN variants, such as Kd-Tree and Ball-Tree. Our results clearly show the performance gains of the proposed solution at 98% when compared to the classic kNN and at least 80% when compared to tree-based approaches.
23
Kininmonth, Stuart J., Glenn De’ath et Hugh P. Possingham. « Graph theoretic topology of the Great but small Barrier Reef world ». Theoretical Ecology 3, no 2 (18 août 2009) : 75–88. http://dx.doi.org/10.1007/s12080-009-0055-3.
Texte intégral
24
Mahmood, Sajidah. « Studying the Wikipedia Math Essential Pages using Graph Theory Metrics ». International Journal of Advances in Soft Computing and its Applications 14, no 1 (28 mars 2022) : 147–58. http://dx.doi.org/10.15849/ijasca.220328.10.
Texte intégralRésumé :
Abstract COVID-19 pandemic enforced students in schools and universities all around the world to study using the online and blinded learning. In these learning models, students depend on the Internet for information searching of different scientific essentials to improve their skills and to overcome the gap of facing instructors. One of the most popular sources of information is Wikipedia. In this work, we attempt to study the relations of different math essential pages of Wikipedia to find the relation between these topics. A graph has been constructed for these pages. The graph theoretical metrics, such as, centrality, edge weights and clustering coefficient have been extracted of the constructed graph. The extracted values have been investigated to gain more insights of the math topics that should be studied first. The extracted results show that the in-degree property of the articles and the betweenness value of these articles are correlated. Moreover, there is no relation between the in /out-degree of the pages. Finally, the constructed graph has a small average shortest path and a high global cluster coefficient. This proves that the constructed graph follows the small world phenomenon. Keywords: Graph metrics, Math essentials, Gephi, Small world phenomenon, Directed graph
25
Wang, Shaoting, Guigang Zhang, Phillip Sheu, Masahiro Hayakawa, Hiroyuki Shigematsu et Atsushi Kitazawa. « Lossy Graph Data Reduction ». International Journal of Semantic Computing 12, no 03 (septembre 2018) : 425–56. http://dx.doi.org/10.1142/s1793351x18500022.
Texte intégralRésumé :
Graphs are widely used nowadays to store complex data of large applications such as social networks, recommendation engines, computer networks, bio-informatics, just to name a few. Graph data reduction plays a very important role in order to store and process such data efficiently. Many studies about graph data reduction have been done, but most of them are focused on lossless reduction in the sense that query results are preserved after reduction. In this paper, we elaborate on the concept of “lossy” graph reduction for applications that may tolerate approximate results with small but bounded errors in exchange for further data reduction. We study one well known graph problem that is the shortest path problem and design the lossy graph reduction algorithms. The error bounds of the algorithms we propose are proved theoretically. In addition, we implement some of the algorithms based on real world data sets to experimentally investigate the impacts of the error tolerance on the reduction ratio.
26
COMBADÃO, JAIME, PAULO R. A. CAMPOS, FRANCISCO DIONISIO et ISABEL GORDO. « Small-world networks decrease the speed of Muller's ratchet ». Genetical Research 89, no 1 (février 2007) : 7–18. http://dx.doi.org/10.1017/s0016672307008658.
Texte intégralRésumé :
Muller's ratchet is an evolutionary process that has been implicated in the extinction of asexual species, the evolution of non-recombining genomes, such as the mitochondria, the degeneration of the Y chromosome, and the evolution of sex and recombination. Here we study the speed of Muller's ratchet in a spatially structured population which is subdivided into many small populations (demes) connected by migration, and distributed on a graph. We studied different types of networks: regular networks (similar to the stepping-stone model), small-world networks and completely random graphs. We show that at the onset of the small-world network – which is characterized by high local connectivity among the demes but low average path length – the speed of the ratchet starts to decrease dramatically. This result is independent of the number of demes considered, but is more pronounced the larger the network and the stronger the deleterious effect of mutations. Furthermore, although the ratchet slows down with increasing migration between demes, the observed decrease in speed is smaller in the stepping-stone model than in small-world networks. As migration rate increases, the structured populations approach, but never reach, the result in the corresponding panmictic population with the same number of individuals. Since small-world networks have been shown to describe well the real contact networks among people, we discuss our results in the light of the evolution of microbes and disease epidemics.
27
Sohn, Insoo. « Small-World and Scale-Free Network Models for IoT Systems ». Mobile Information Systems 2017 (2017) : 1–9. http://dx.doi.org/10.1155/2017/6752048.
Texte intégralRésumé :
It is expected that Internet of Things (IoT) revolution will enable new solutions and business for consumers and entrepreneurs by connecting billions of physical world devices with varying capabilities. However, for successful realization of IoT, challenges such as heterogeneous connectivity, ubiquitous coverage, reduced network and device complexity, enhanced power savings, and enhanced resource management have to be solved. All these challenges are heavily impacted by the IoT network topology supported by massive number of connected devices. Small-world networks and scale-free networks are important complex network models with massive number of nodes and have been actively used to study the network topology of brain networks, social networks, and wireless networks. These models, also, have been applied to IoT networks to enhance synchronization, error tolerance, and more. However, due to interdisciplinary nature of the network science, with heavy emphasis on graph theory, it is not easy to study the various tools provided by complex network models. Therefore, in this paper, we attempt to introduce basic concepts of graph theory, including small-world networks and scale-free networks, and provide system models that can be easily implemented to be used as a powerful tool in solving various research problems related to IoT.
28
El-Mesady, Ahmed, Aleksandr Y. Romanov, Aleksandr A. Amerikanov et Alexander D. Ivannikov. « On Bipartite Circulant Graph Decompositions Based on Cartesian and Tensor Products with Novel Topologies and Deadlock-Free Routing ». Algorithms 16, no 1 (22 décembre 2022) : 10. http://dx.doi.org/10.3390/a16010010.
Texte intégralRésumé :
Recent developments in commutative algebra, linear algebra, and graph theory allow us to approach various issues in several fields. Circulant graphs now have a wider range of practical uses, including as the foundation for optical networks, discrete cellular neural networks, small-world networks, models of chemical reactions, supercomputing and multiprocessor systems. Herein, we are concerned with the decompositions of the bipartite circulant graphs. We propose the Cartesian and tensor product approaches as helping tools for the decompositions. The proposed approaches enable us to decompose the bipartite circulant graphs into many categories of graphs. We consider the use cases of applying the described theory of bipartite circulant graph decomposition to the problems of finding new topologies and deadlock-free routing in them when building supercomputers and networks-on-chip.
29
Wu-Yan, Elena, Richard F. Betzel, Evelyn Tang, Shi Gu, Fabio Pasqualetti et Danielle S. Bassett. « Benchmarking Measures of Network Controllability on Canonical Graph Models ». Journal of Nonlinear Science 30, no 5 (9 mars 2018) : 2195–233. http://dx.doi.org/10.1007/s00332-018-9448-z.
Texte intégralRésumé :
Abstract The control of networked dynamical systems opens the possibility for new discoveries and therapies in systems biology and neuroscience. Recent theoretical advances provide candidate mechanisms by which a system can be driven from one pre-specified state to another, and computational approaches provide tools to test those mechanisms in real-world systems. Despite already having been applied to study network systems in biology and neuroscience, the practical performance of these tools and associated measures on simple networks with pre-specified structure has yet to be assessed. Here, we study the behavior of four control metrics (global, average, modal, and boundary controllability) on eight canonical graphs (including Erdős–Rényi, regular, small-world, random geometric, Barábasi–Albert preferential attachment, and several modular networks) with different edge weighting schemes (Gaussian, power-law, and two nonparametric distributions from brain networks, as examples of real-world systems). We observe that differences in global controllability across graph models are more salient when edge weight distributions are heavy-tailed as opposed to normal. In contrast, differences in average, modal, and boundary controllability across graph models (as well as across nodes in the graph) are more salient when edge weight distributions are less heavy-tailed. Across graph models and edge weighting schemes, average and modal controllability are negatively correlated with one another across nodes; yet, across graph instances, the relation between average and modal controllability can be positive, negative, or nonsignificant. Collectively, these findings demonstrate that controllability statistics (and their relations) differ across graphs with different topologies and that these differences can be muted or accentuated by differences in the edge weight distributions. More generally, our numerical studies motivate future analytical efforts to better understand the mathematical underpinnings of the relationship between graph topology and control, as well as efforts to design networks with specific control profiles.
30
WANG, DAOHUA, YUMEI XUE, QIAN ZHANG et MIN NIU. « SCALE-FREE AND SMALL-WORLD PROPERTIES OF A SPECIAL HIERARCHICAL NETWORK ». Fractals 27, no 02 (mars 2019) : 1950010. http://dx.doi.org/10.1142/s0218348x19500105.
Texte intégralRésumé :
Many real systems behave similarly with scale-free and small-world structures. In this paper, we generate a special hierarchical network and based on the particular construction of the graph, we aim to present a study on some properties, such as the clustering coefficient, average path length and degree distribution of it, which shows the scale-free and small-world effects of this network.
31
Caliandro, Pietro, Fabrizio Vecchio, Francesca Miraglia, Giuseppe Reale, Giacomo Della Marca, Giuseppe La Torre, Giordano Lacidogna et al. « Small-World Characteristics of Cortical Connectivity Changes in Acute Stroke ». Neurorehabilitation and Neural Repair 31, no 1 (20 août 2016) : 81–94. http://dx.doi.org/10.1177/1545968316662525.
Texte intégralRésumé :
Background. After cerebral ischemia, disruption and subsequent reorganization of functional connections occur both locally and remote to the lesion. Recently, complexity of brain connectivity has been described using graph theory, a mathematical approach that depicts important properties of complex systems by quantifying topologies of network representations. Functional and dynamic changes of brain connectivity can be reliably analyzed via electroencephalography (EEG) recordings even when they are not yet reflected in structural changes of connections. Objective. We tested whether and how ischemic stroke in the acute stage may determine changes in small-worldness of cortical networks as measured by cortical sources of EEG. Methods. Graph characteristics of EEG of 30 consecutive stroke patients in acute stage (no more than 5 days after the event) were examined. Connectivity analysis was performed using eLORETA in both hemispheres. Results. Network rearrangements were mainly detected in delta, theta, and alpha bands when patients were compared with healthy subjects. In delta and alpha bands similar findings were observed in both hemispheres regardless of the side of ischemic lesion: bilaterally decreased small-worldness in the delta band and bilaterally increased small-worldness in the alpha2 band. In the theta band, bilaterally decreased small-worldness was observed only in patients with stroke in the left hemisphere. Conclusions. After an acute stroke, brain cortex rearranges its network connections diffusely, in a frequency-dependent modality probably in order to face the new anatomical and functional frame.
32
ADDARIO-BERRY, LOUIGI, SVANTE JANSON et COLIN McDIARMID. « On the Spread of Random Graphs ». Combinatorics, Probability and Computing 23, no 4 (13 juin 2014) : 477–504. http://dx.doi.org/10.1017/s0963548314000248.
Texte intégralRésumé :
The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdős–Rényi random graphs Gn,p in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical Gn,p, we show that if p=c/n with c>1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n. Further, we show that for d large, with high probability the spread of G(n,d) becomes arbitrarily close to that of the complete graph $\mathsf{K}_n$.
33
Zhao, Zongya, Yaqing Cheng, Zhenxin Li et Yi Yu. « Altered Small-World Networks in First-Episode Schizophrenia Patients during Cool Executive Function Task ». Behavioural Neurology 2018 (5 septembre 2018) : 1–11. http://dx.doi.org/10.1155/2018/2191208.
Texte intégralRésumé :
At present, little is known about brain functional connectivity and its small-world topologic properties in first-episode schizophrenia (SZ) patients during cool executive function task. In this paper, the Trail Making Test-B (TMT-B) task was used to evaluate the cool executive function of first-episode SZ patients and electroencephalography (EEG) data were recorded from 14 first-episode SZ patients and 14 healthy controls during this cool executive function task. Brain functional connectivity between all pairs of EEG channels was constructed based on mutual information (MI) analysis. The constructed brain functional networks were filtered by three thresholding schemes: absolute threshold, mean degree, and a novel data-driven scheme based on orthogonal minimal spanning trees (OMST), and graph theory was then used to study the topographical characteristics of the filtered brain graphs. Results indicated that the graph theoretical measures of the theta band showed obvious difference between SZ patients and healthy controls. In the theta band, the characteristic path length was significantly longer and the cluster coefficient was significantly smaller in the SZ patients for a wide range of absolute threshold T. However, the cluster coefficient showed no significant changes, and the characteristic path length was still significantly longer in SZ patients when calculated as a function of mean degree K. Interestingly, we also found that only the characteristic path length was significantly longer in SZ patients compared with healthy controls after using the OMST scheme. Pearson correlation analysis showed that the characteristic path length was positively correlated with executive time of TMT-B for the combined SZ patients and healthy controls (r=0.507, P=0.006), but not for SZ patients alone (r=0.072, P=0.612). The above results suggested a less optimal organization of the brain network and could be useful for understanding the pathophysiologic mechanisms underlying cool executive dysfunction in first-episode SZ patients.
34
Kumari, Neetu, et Anshul Verma. « Analysis of Oncogene Protein Structure Using Small World Network Concept ». Current Bioinformatics 15, no 7 (15 décembre 2020) : 732–40. http://dx.doi.org/10.2174/1574893614666191113143840.
Texte intégralRésumé :
Background: The basic building block of a body is protein which is a complex system whose structure plays a key role in activation, catalysis, messaging and disease states. Therefore, careful investigation of protein structure is necessary for the diagnosis of diseases and for the drug designing. Protein structures are described at their different levels of complexity: primary (chain), secondary (helical), tertiary (3D), and quaternary structure. Analyzing complex 3D structure of protein is a difficult task but it can be analyzed as a network of interconnection between its component, where amino acids are considered as nodes and interconnection between them are edges. Objective: Many literature works have proven that the small world network concept provides many new opportunities to investigate network of biological systems. The objective of this paper is analyzing the protein structure using small world concept. Methods: Protein is analyzed using small world network concept, specifically where extreme condition is having a degree distribution which follows power law. For the correct verification of the proposed approach, dataset of the Oncogene protein structure is analyzed using Python programming. Results: Protein structure is plotted as network of amino acids (Residue Interaction Graph (RIG)) using distance matrix of nodes with given threshold, then various centrality measures (i.e., degree distribution, Degree-Betweenness correlation, and Betweenness-Closeness correlation) are calculated for 1323 nodes and graphs are plotted. Conclusion: Ultimately, it is concluded that there exist hubs with higher centrality degree but less in number, and they are expected to be robust toward harmful effects of mutations with new functions.
35
Addario-Berry, Louigi, et Tao Lei. « The Mixing Time of the Newman-Watts Small-World Model ». Advances in Applied Probability 47, no 1 (mars 2015) : 37–56. http://dx.doi.org/10.1239/aap/1427814580.
Texte intégralRésumé :
‘Small worlds’ are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman-Watts small-world model, the mixing time is of order log2n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2n and an upper bound of order log3n.
36
Addario-Berry, Louigi, et Tao Lei. « The Mixing Time of the Newman-Watts Small-World Model ». Advances in Applied Probability 47, no 01 (mars 2015) : 37–56. http://dx.doi.org/10.1017/s0001867800007692.
Texte intégralRésumé :
‘Small worlds’ are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman-Watts small-world model, the mixing time is of order log2 n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2 n and an upper bound of order log3 n.
37
Cai, Shaowei, Jinkun Lin et Chuan Luo. « Finding A Small Vertex Cover in Massive Sparse Graphs : Construct, Local Search, and Preprocess ». Journal of Artificial Intelligence Research 59 (31 juillet 2017) : 463–94. http://dx.doi.org/10.1613/jair.5443.
Texte intégralRésumé :
The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.
38
Zhang, Zhanqi, et Yingqing Xiao. « Graph Concatenations to Derive Weighted Fractal Networks ». Complexity 2020 (18 juillet 2020) : 1–9. http://dx.doi.org/10.1155/2020/4906878.
Texte intégralRésumé :
Given an initial weighted graph G0, an integer m>1, and m scaling factors f1,…,fm∈0,1, we define a sequence of weighted graphs Gkk=0∞ iteratively. Provided that Gk−1 is given for k≥1, we let Gk−11,…,Gk−1m be m copies of Gk−1, whose weighted edges have been scaled by f1,…,fm, respectively. Then, Gk is constructed by concatenating G0 with all the m copies. The proposed framework shares several properties with fractal sets, and the similarity dimension dfract has a great impact on the topology of the graphs Gk (e.g., node strength distribution). Moreover, the average geodesic distance of Gk increases logarithmically with the system size; thus, this framework also generates the small-world property.
39
Ghorbani, Modjtaba, et Matthias Dehmer. « Network Analyzing by the Aid of Orbit Polynomial ». Symmetry 13, no 5 (4 mai 2021) : 801. http://dx.doi.org/10.3390/sym13050801.
Texte intégralRésumé :
This article aims to be a further contribution to the research on structural complexity networks. Here, we emphasize measures to determine symmetry. The so-called “orbit polynomial” is defined by OG(x)=∑iaixi, where ai is the number of orbits of size i. Furthermore, the graph polynomial 1−OG(x) has a unique positive root in the interval (0,1), which can be considered as a relevant measure of the symmetry of a graph. In the present paper, we studied some properties of the orbit polynomial with respect to the stabilizer elements of each vertex. Furthermore, we constructed graphs with a small number of orbits and characterized some classes of graphs in terms of calculating their orbit polynomials. We studied the symmetry structure of well-known real-world networks in terms of the orbit polynomial.
40
Michel, Jesse, Sushruth Reddy, Rikhav Shah, Sandeep Silwal et Ramis Movassagh. « Directed random geometric graphs ». Journal of Complex Networks 7, no 5 (8 avril 2019) : 792–816. http://dx.doi.org/10.1093/comnet/cnz006.
Texte intégralRésumé :
Abstract Many real-world networks are intrinsically directed. Such networks include activation of genes, hyperlinks on the internet and the network of followers on Twitter among many others. The challenge, however, is to create a network model that has many of the properties of real-world networks such as power-law degree distributions and the small-world property. To meet these challenges, we introduce the Directed Random Geometric Graph (DRGG) model, which is an extension of the random geometric graph model. We prove that it is scale-free with respect to the indegree distribution, has binomial outdegree distribution, has a high clustering coefficient, has few edges and is likely small-world. These are some of the main features of aforementioned real-world networks. We also empirically observed that word association networks have many of the theoretical properties of the DRGG model.
41
John, Majnu, Toshikazu Ikuta et Janina Ferbinteanu. « Graph analysis of structural brain networks in Alzheimer’s disease : beyond small world properties ». Brain Structure and Function 222, no 2 (29 juin 2016) : 923–42. http://dx.doi.org/10.1007/s00429-016-1255-4.
Texte intégral
42
Vega-Oliveros, Didier A., José Nascimento, Bahram Lavi et Anderson Rocha. « Real-world-events data sifting through ultra-small labeled datasets and graph fusion ». Applied Soft Computing 132 (janvier 2023) : 109865. http://dx.doi.org/10.1016/j.asoc.2022.109865.
Texte intégral
43
Baydilli, Yusuf Yargi, et İlker Türker. « Is the world small enough ? — A view from currencies ». International Journal of Modern Physics B 33, no 12 (10 mai 2019) : 1950120. http://dx.doi.org/10.1142/s0217979219501200.
Texte intégralRésumé :
Exchange rates are important indicators of the economic power of countries, directly affected by the international trading patterns and relations. Since almost every pair of countries in the globalized world are economically and financially related, exchange rates can be evaluated as nodes of a global financial network to make meaningful inferences. In this study, a financial network approach is conducted by evaluating the movements of the most traded 35 currencies against gold between years 2005 and 2017. Using graph theory and statistical methods, the analysis of economic relations between currencies is carried out, supported with geographical and cultural inferences. A risk map of currencies is generated through the portfolio optimization. Another approach of applying various threshold levels for correlations to determine connections between currencies is also employed. Results indicate that there exists a saddle point for correlation threshold as 0.9 which results in a robust network topology that is highly modular and clustered, also dominantly displaying small-world and scale-free properties.
44
Duan, Yijun, Xin Liu, Adam Jatowt, Hai-tao Yu, Steven Lynden, Kyoung-Sook Kim et Akiyoshi Matono. « Long-Tailed Graph Representation Learning via Dual Cost-Sensitive Graph Convolutional Network ». Remote Sensing 14, no 14 (8 juillet 2022) : 3295. http://dx.doi.org/10.3390/rs14143295.
Texte intégralRésumé :
Deep learning algorithms have seen a massive rise in popularity for remote sensing over the past few years. Recently, studies on applying deep learning techniques to graph data in remote sensing (e.g., public transport networks) have been conducted. In graph node classification tasks, traditional graph neural network (GNN) models assume that different types of misclassifications have an equal loss and thus seek to maximize the posterior probability of the sample nodes under labeled classes. The graph data used in realistic scenarios tend to follow unbalanced long-tailed class distributions, where a few majority classes contain most of the vertices and the minority classes contain only a small number of nodes, making it difficult for the GNN to accurately predict the minority class samples owing to the classification tendency of the majority classes. In this paper, we propose a dual cost-sensitive graph convolutional network (DCSGCN) model. The DCSGCN is a two-tower model containing two subnetworks that compute the posterior probability and the misclassification cost. The model uses the cost as ”complementary information” in a prediction to correct the posterior probability under the perspective of minimal risk. Furthermore, we propose a new method for computing the node cost labels based on topological graph information and the node class distribution. The results of extensive experiments demonstrate that DCSGCN outperformed other competitive baselines on different real-world imbalanced long-tailed graphs.
45
Suzuki, Tomoya, Kazuhiro Hiwada, Hirotsugu Kajihara, Shintaro Sano, Shuou Nomura et Tatsuo Shiozawa. « Approaching DRAM performance by using microsecond-latency flash memory for small-sized random read accesses ». Proceedings of the VLDB Endowment 14, no 8 (avril 2021) : 1311–24. http://dx.doi.org/10.14778/3457390.3457397.
Texte intégralRésumé :
For applications in which small-sized random accesses frequently occur for datasets that exceed DRAM capacity, placing the datasets on SSD can result in poor application performance. For the read-intensive case we focus on in this paper, low latency flash memory with microsecond read latency is a promising solution. However, when they are used in large numbers to achieve high IOPS (Input/Output operations Per Second), the CPU processing involved in IO requests is an overhead. To tackle the problem, we propose a new access method combining two approaches: 1) optimizing issuance and completion of the IO requests to reduce the CPU overhead. 2) utilizing many contexts with lightweight context switches by stackless coroutines. These reduce the CPU overhead per request to less than 10 ns, enabling read access with DRAM-like overhead, while the access latency longer than DRAM can be hidden by the context switches. We apply the proposed method to graph algorithms such as BFS (Breadth First Search), which involves many small-sized random read accesses. In our evaluation, the large graph data is placed on microsecond-latency flash memories within prototype boards, and it is accessed by the proposed method. As a result, for the synthetic and real-world graphs, the execution times of the graph algorithms are 88--141% of those when all the data are placed in DRAM.
46
Ikeda, Nobutoshi. « Fractal behaviours of networks induced on infinite tree structures by random walks ». Journal of Physics : Conference Series 2090, no 1 (1 novembre 2021) : 012085. http://dx.doi.org/10.1088/1742-6596/2090/1/012085.
Texte intégralRésumé :
Abstract Tree graphs such as Cayley trees provide a stage to support the self-organization of fractal networks by the flow of walkers from the root vertex to the outermost shell of the tree graph. This network model is a typical example that demonstrates the ability of a random process on a network to generate fractality. However, the finite scale of the tree structure assumed in the model restricts the size of fractal networks. In this study, we removed the restriction on the size of the trees by introducing a lifetime τ (number of steps of random walks) of walkers. As a result, we successfully induced a size-independent fractal structure on a tree graph without a boundary. Our numerical results show that the mean number of offspring d b of the original tree structure determines the value of the fractal box dimension db through the relation d b — 1 = (n b — 1) -θ . The lifetime τ controls the presence or absence of small-world and scale-free properties. The ideal fractal behaviour can be maintained by selecting an appropriate value of τ. The numerical results contribute to the development of a systematic method for generating fractal small-world and scale-free networks while controlling the value of the fractal box dimension. Unlike other models that use recursive rules to generate self-similar structures, this model specifically produces small-world fractal networks with scale-free properties.
47
Bärmann, Andreas, Patrick Gemander, Alexander Martin et Maximilian Merkert. « On Recognizing Staircase Compatibility ». Journal of Optimization Theory and Applications 195, no 2 (29 octobre 2022) : 449–79. http://dx.doi.org/10.1007/s10957-022-02091-2.
Texte intégralRésumé :
AbstractFor the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite graphs as a subproblem, it allows for totally unimodular linear programming formulations, which have shown to efficiently solve problems from different applications. In this work, we address questions concerning the recognizability of this property in the case where the m-partition of the graph is given, but suitable total orders are to be determined. While finding these total orders is NP-hard in general, we give several conditions under which it can be done in polynomial time. For bipartite graphs, we present a polynomial-time algorithm to recognize staircase compatibility and show that staircase total orders are unique up to a small set of reordering operations. On m-partite graphs, where the recognition problem is NP-complete in the general case, we identify a polynomially solvable subcase and also provide a corresponding algorithm to compute the total orders. Finally, we evaluate the performance of our ordering algorithm for m-partite graphs on a set of artificial instances as well as real-world instances from a railway timetabling application. It turns out that applying the ordering algorithm to the real-world instances and subsequently solving the problem via the aforementioned totally unimodular reformulations indeed outperforms a generic formulation which does not exploit staircase compatibility.
48
Brinkley, Catherine. « The Small World of the Alternative Food Network ». Sustainability 10, no 8 (17 août 2018) : 2921. http://dx.doi.org/10.3390/su10082921.
Texte intégralRésumé :
This research offers the first use of graph theory mathematics in social network analysis to explore relationships built through an alternative food network. The local food system is visualized using geo-social data from 110 farms and 224 markets around Baltimore County, Maryland, with 699 connections between them. Network behavior is explored through policy document review and interviews. The findings revealed a small-world architecture, with system resiliency built-in by diversified marketing practices at central nodes. This robust network design helps to explain the long-term survival of local food systems despite the meteoric rise of global industrial food supply chains. Modern alternative food networks are an example of a movement that seeks to reorient economic power structures in response to a variety of food system-related issues not limited to consumer health but including environmental impacts. Uncovering the underlying network architecture of this sustainability-oriented social movement helps reveal how it weaves systemic change more broadly. The methods used in this study demonstrate how social values, social networks, markets, and governance systems embed to transform both physical landscapes and human bodies. Network actors crafted informal policy reports, which were directly incorporated in state and local official land-use and economic planning documents. Community governance over land-use policy suggests a powerful mechanism for further localizing food systems.
49
Zhang, Xun, Lanyan Yang, Bin Zhang, Ying Liu, Dong Jiang, Xiaohai Qin et Mengmeng Hao. « Multi-Scale Aggregation Graph Neural Networks Based on Feature Similarity for Semi-Supervised Learning ». Entropy 23, no 4 (28 mars 2021) : 403. http://dx.doi.org/10.3390/e23040403.
Texte intégralRésumé :
The problem of extracting meaningful data through graph analysis spans a range of different fields, such as social networks, knowledge graphs, citation networks, the World Wide Web, and so on. As increasingly structured data become available, the importance of being able to effectively mine and learn from such data continues to grow. In this paper, we propose the multi-scale aggregation graph neural network based on feature similarity (MAGN), a novel graph neural network defined in the vertex domain. Our model provides a simple and general semi-supervised learning method for graph-structured data, in which only a very small part of the data is labeled as the training set. We first construct a similarity matrix by calculating the similarity of original features between all adjacent node pairs, and then generate a set of feature extractors utilizing the similarity matrix to perform multi-scale feature propagation on graphs. The output of multi-scale feature propagation is finally aggregated by using the mean-pooling operation. Our method aims to improve the model representation ability via multi-scale neighborhood aggregation based on feature similarity. Extensive experimental evaluation on various open benchmarks shows the competitive performance of our method compared to a variety of popular architectures.
50
Ma, Fei, et Bing Yao. « A family of small-world network models built by complete graph and iteration-function ». Physica A : Statistical Mechanics and its Applications 492 (février 2018) : 2205–19. http://dx.doi.org/10.1016/j.physa.2017.11.136.
Texte intégral