Academic literature on the topic 'Graphe massifs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graphe massifs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Graphe massifs"
1
Beltek, M., and O. Frolov. "Determination of the influence of the degree of fracturing of the rock mass on the index of reduction of its strength." Collection of Research Papers of the National Mining University 74 (September 2023): 7–18. http://dx.doi.org/10.33271/crpnmu/74.007.
Full textAbstract:
Purpose. The purpose of research of the presented scientific publication is to establish the regularity of changes in the generalized coefficient of strength reduction of disturbed rock massif depending on the degree of rock fracturing. Research methodology. To solve the set tasks we applied a complex approach, which consists in the analysis and generalization of previous studies on the study of the change in the strength of the rock massif depending on the degree of fracturing, scientific and technical justification of the possibility of generalizing the studied strength indicators of the disturbed massif, approximation of graphs of the change in the structural weakening coefficient, RQD and RMR depending on the fracture modulus. Research results. Scientific data of domestic scientists on determining the value of the structural weakening coefficient depending on the factors affecting the overall strength of the rock massif, and foreign scientists on establishing indicators of the state of disturbed rock massifs have been analyzed. To summarize the results of the presented assessment methods, the changes in the structural weakening coefficient, RQD and RMR indices depending on the fracture modulus of the rock massif are combined in one graph. Alignment of the mentioned graphical dependences showed the identical character of their changes. The curve of approximation (trend) for graphical dependences of the structural weakening coefficient, RQD and RMR on the fracture modulus, which can be described by a polynomial of the 3rd degree, has been obtained and the value of approximation reliability R²= 0.8975 has been established. Scientific novelty. The idea of methods and indicators for assessing the state of disturbance of rock massifs depending on various factors has been developed. The analytical dependence of the change of the generalized coefficient of strength reduction of a rocky rock massif on the fracture modulus has been obtained. Practical significance. The established influence of rock fracture modulus on the degree of strength reduction of rock massif allows to determine reliable data on the condition of ledges and sides of the quarry and to develop organizational and technical measures for further development of technology of their mining.
2
Dmitrienko, Vladimir, Nadejda Dmitrienko, and Аleksandr Bogomazov. "Impact of “wet conservation” of mining enterprises on constructing buildings of lightweight materials." E3S Web of Conferences 284 (2021): 05013. http://dx.doi.org/10.1051/e3sconf/202128405013.
Full textAbstract:
The analysis of the influence of flooding of the developed areas of closed mining enterprises on the mechanical characteristics of clay rocks is given. The deformation characteristics of clay shale under prolonged moistening conditions have been experimentally established and proved. Simulation of stress-strain state of soil massifs and building structures by method of finite elements is considered and the influence of power of developed spaces on settlement of building foundations of buildings of light materials is established. The distribution of vertical displacements in the rock massif is presented, the graphs of the dependence of the foundation settlement on the excavation power are plotted, the excess of the standard values of settlement is noted when buildings are located directly above the preparing workings.
3
Dongak, Dzhamil Aiyr-Sanaaevich, Artysh Valerievich Mongush, Chinchi Buyanovna Mongush, and Shydar Orlanovich Chuldum. "A distance study of seasonal dynamics of the vegetation index (NVDI) of the Mongun-Taiga massif vegetation cover." Samara Journal of Science 11, no. 4 (December 1, 2022): 22–29. http://dx.doi.org/10.55355/snv2022114103.
Full textAbstract:
This paper analyzes seasonal dynamics of the Mongun-Taiga massif vegetation cover from February to October 2022 based on the application of the NDVI vegetation index using Sentinel-2 satellite imagery data. To analyze the seasonal dynamics of the vegetation index of the Mongun-Taiga massif, 15 points on the valleys of five rivers were selected they are the Tolaity River (south side), the Holash River (west side), the Balyktyg River (north side), the Right-Mugur River (north-east side) and the Shara-Khoragai river (east side). The graphs of the vegetation cover of different exposures of the massif slopes show that the highest values are represented at the western side of the massif (the Holash River), then on the southern side (the Tolaity River) and then on the northern side of the massif (the Balyktyg River). The valleys of the Shara-Khoragai River (east side) and the Right-Mugur River (north-east side) have the lowest indicators of vegetation cover. Different curves of the vegetation cover graphs for different exposures of the massif explain that the climate in this area is very complex. Terrain, slope exposures, humidity, strength and direction of winds, sunlight, temperature, slopes of selected points, as well as watercourses affect vegetation cover differently. For a more thorough study, it is necessary to obtain higher-resolution images and conduct ground-based measurement work to assess the state of the vegetation cover of the massif and obtain accurate meteorological data.
4
Ter-Martirosyan, Zaven G., Armen Z. Ter-Martirosyan, and Yuliya V. Vanina. "Long-term settlement and bearing capacity of foundations adjacent to vertical excavation at various parameters of soil viscosity." Vestnik MGSU, no. 12 (December 2022): 1664–76. http://dx.doi.org/10.22227/1997-0935.2022.12.1664-1676.
Full textAbstract:
Introduction. When the underground part of a high-rise building interacts with the surrounding soil massif behind the excavation pit, a complex heterogeneous stress-strain state occurs, transforming in space and time — during construction and during the exploitation of the building. Special issues arise when the soil massif is heterogeneous and has rheological properties, and an additional load acts near the pit excavation at the same time.
Materials and methods. For the problem of the stress strain statement of soil with a weight behind the enclosure of a pit with a depth h, taking into account the influence of a distributed load q = const with a width b = 2a at a distance c from the edge of the enclosing structure of the pit, the stress components were obtained using a solution based on the Ribier – Filon trigonometric series. To determine the settlement over time of the foundation near the pit, the A.Z. Ter-Martirosyan’s model was used. To describe shear deformations and the Kelvin – Foigt’s model was used to describe volume deformations, assuming that ε.z(t) = ε.v(t) + ε.γ(t), according to the Henky’s system of physical equations.
Results. An analytical method has been developed for quantifying the settlement of soil bases and foundations of nearby buildings behind the pit over the time. The graphs of the settlement-time with double curvature, as well as the graph of the long-term stability of the base are obtained.
Conclusions. The solutions obtained can be used to determine the long-term settlements and bearing capacity of the foundations of buildings and structures with rheological properties near the pits. The selected geomechanical model of the foundation (its geometric parameters, initial and boundary conditions), as well as the computational model of the soil (linear, nonlinear and rheological) and the type of physical equations (Hooke system or Henky system), significantly affect the type of the settlement-time curve (S–t), as well as the bearing capacity of the soils. Collaborative using of A.Z. Ter-Martirosyan’s rheological model and Kelvin – Foigt’s rheological model makes it possible to obtain settlement-time graphs with double curvature, as well as a graph of the long-term stability of the soil base.
5
Kuzmenko, Eduard, Sergiy Bagriy, Inna Artym, and Volodymyr Artym. "GEODYNAMICS." GEODYNAMICS 2(33)2022, no. 2(33) (2022): 64–74. http://dx.doi.org/10.23939/jgd2022.02.065.
Full textAbstract:
The purpose of the research is to substantiate the theoretical prerequisites for the interpretation of the geophysical method of the Earth's natural pulsed electromagnetic field (ENPEMF). The justification will be performed by quantifying the stress state of the rock massif, modeling of the obtained analytical dependencies for disturbed massifs. The basis for the interpretation is the coordination of the obtained distributions of intensity with the intensity of the electromagnetic field. The initial data are classical formulas of theoretical mechanics, modified to the conditions of the geological structure of the object of research and long-term research by the method of ENPEMF at the object – Kalush-Golynsky potassium salt deposit in the Pre-Carpathian. The research methodology included the development and presentation of models of the stress-strain state of the mining area, followed by the calculation of specific distributions of stress and analysis of their relationship with the dynamics of ENPEMF for specific areas of regime observations. The results of the research are given in the following sequence: 1) an example of calculating model stresses; 2) practical results of ENPEMF; 3) comparison of theoretical model calculations and real observations' data. Examples of calculations are given for a rock massif including a rectangular-shaped mining operation located in a salt formation. The distribution of stresses is calculated for the 2D model, taking into account the actual physical parameters. The series of graphs shows the change in tension both along the profile and with depth. The model is complicated for a variant of two chambers located at different depths. Observation of ENPEMF is demonstrated for a complex section of rocks. Actual plots of the field intensity with a high degree of correlation correspond to the calculated plots at a certain depth. The complication of the section and the presence of different stages of the postoperative period, which is reflected in the regime observations, leads to the deviation of the form of the graphs from the "ideal-model", but at the qualitative level this form corresponds to the theoretical one. The novelty lies in the development of the principles of quantitative assessment of the stress-strain state of the disturbed rock mass as the basis for the theoretical assessment of the distribution of the natural pulsed electromagnetic field of the Earth. In particular, the identity of the results of practical geophysical observations and computational models of the stress-strain state is demonstrated. The results obtained should be considered as a contribution to the theoretical basis of the quantitative interpretation principles of the geophysical method of ENPEMF. At the same time, the ways of further research for the full implementation of this research area are indicated.
6
Sokornov, Anton, Aleksandr Kon'kov, Anatoliy Novikov, and Andrey Benin. "Factors Affecting Additional Pressure Distribution from Ground Construction on Subway Tunnels." Proceedings of Petersburg Transport University 19, no. 2 (June 22, 2022): 367–77. http://dx.doi.org/10.20295/1815-588x-2022-19-2-367-377.
Full textAbstract:
Purpose: To analyze the factors affecting pressure distribution from ground construction on subway tunnel linings. Method: Mathematical modeling by finite element method of a system that includes a soil massif, an interstation tunnel lining and a load from ground building foundation. Results: The type of additional pressure distribution graph from ground construction inviolate massif and in the massif, which stress-strain state is distorted by tunneling, is established. It is found that the change of additional pressure is directly proportional to load change as by depth as well as by distance from foundation axis; this law is preserved at any other parameter change (in inviolate soil massif and in the massif which stress-strain state is changed by tunneling, at various ways of tunneling modeling, at the use of various geomechanical soil models). It is established that the value of additional pressure from ground construction practically doesn’t depend on tunneling modeling method. The difference between the results at soil description via Mohr-Coulomb model and via its modification is substantiated. Practical importance: It is shown the possibility to determine accurately the amount of additional pressure from ground construction on tunnel lining without having information on tunneling method.
7
Alkhdour, Ahmad, Anatolii Radkevych, Oleksii Tiutkin, and Nataliia Bondarenko. "Prediction of the stress-strain state of circular workings in a layered massif by scaling." E3S Web of Conferences 168 (2020): 00020. http://dx.doi.org/10.1051/e3sconf/202016800020.
Full textAbstract:
The scientific and technical task for determining the stress-strain state of mine workings is complicated by the presence of a layered massif. This task assumes particular importance in the case of circular tunneling. During its operation, it is important to predict the change of the stressstrain state for the massif or to carry out the prompt determination in the change of stresses and displacements for the unsupported working. The solution of this geomechanical task allows performing geometrical matching of the working, ensuring its strength and stability in the layered massif. A numerical finite element method based on StructureCAD (SCAD) software package was used to solve it. Four geomechanical systems were calculated: “unsupported working – layered massif”. Owing to the obtained results, graphs of stresses and displacements were constructed, which allow to determine these parameters for workings with different geometric parameters and X-parameter characterizing the ratio of the elasticity modulus of the matrix and the layer. Obtained regularities of change of stresses and displacements for the unsupported working when zooming made it possible to introduce scaling-parameters, which are a dimensionless ratio of the radii for a real system and a system with a unit diameter.
8
Vidal, Muriel, Daniel Goujet, Philippe Janvier, and Hubert Lardeux. "Micro-restes de Vertébrés du Calcaire de La Grange, Dévonien inférieur (Emsien) du Sud-Est du Massif Armoricain [Fish remains from the La Grange Limestone, Lower Devonian (Emsian), South-Eastern Armorican Massif." Neues Jahrbuch für Geologie und Paläontologie - Abhandlungen 194, no. 2-3 (December 21, 1994): 321–41. http://dx.doi.org/10.1127/njgpa/194/1994/321.
Full text
9
Atrassi, Fatima E. L., Fabrice Brunet, Mohamed Bouybaouene, Christian Chopin, and Gilles Chazot. "Melting textures and microdiamonds preserved in graphite pseudomorphs from the Beni Bousera peridotite massif, Morocco." European Journal of Mineralogy 23, no. 2 (May 3, 2011): 157–68. http://dx.doi.org/10.1127/0935-1221/2011/0023-2094.
Full text
10
Subbotin, Ignat. "Discrete and continuous models in calculating the bearing capacity of soil massifs reinforced with geosynthetics." Construction and Architecture 8, no. 4 (October 15, 2020): 28–36. http://dx.doi.org/10.29039/2308-0191-2020-8-4-28-36.
Full textAbstract:
The article discusses continuous and discrete models of the soil environment on the examples of calculations under the action of a strip load with surcharge on a plane. The options for calculating both slopes and soil base for foundations in natural, artificial and composite environments are considered. A theoretical method for calculating the bearing capacity of a composite medium of a subsoil that is anisotropic in shear resistance is presented. Formulas and graphs of the results of calculating the compared soil conditions are given and their quantitative assessment of strength in comparison with the natural environment is given.
Dissertations / Theses on the topic "Graphe massifs"
1
Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.
Full textAbstract:
L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’artQuerying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms
2
Bletterer, Arnaud. "Une approche basée graphes pour la modélisation et le traitement de nuages de points massifs issus d’acquisitions de LiDARs terrestres." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4218/document.
Full textAbstract:
Avec l'évolution des dispositifs d'acquisition 3D, les nuages de points sont maintenant devenus une représentation essentielle des scènes numérisées. Les systèmes récents sont capables de capturer plusieurs centaines de millions de points en une seule acquisition. Comme plusieurs acquisitions sont nécessaires pour capturer la géométrie de scènes de grande taille, un site historique par exemple, nous obtenons des nuages de points massifs, i.e., composés de plusieurs milliards de points. Dans cette thèse, nous nous intéressons à la structuration et à la manipulation de nuages de points issus d'acquisitions générées à partir de LiDARs terrestres. A partir de la structure de chaque acquisition, des graphes, représentant chacun la connectivité locale de la surface numérisée, sont construits. Les graphes créés sont ensuite liés entre eux afin d'obtenir une représentation globale de la surface capturée. Nous montrons que cette structure est particulièrement adaptée à la manipulation de la surface sous-jacente aux nuages de points massifs, même sur des ordinateurs ayant une mémoire limitée. Notamment, nous montrons que cette structure permet de traiter deux problèmes spécifiques à ce type de données. Un premier lié au ré-échantillonnage de nuages de points, en générant des distributions de bonne qualité en termes de bruit bleu grâce à un algorithme d'échantillonnage en disques de Poisson. Un autre lié à la construction de diagrammes de Voronoï centroïdaux, permettant l'amélioration de la qualité des distributions générées, ainsi que la reconstruction de maillages triangulairesWith the evolution of 3D acquisition devices, point clouds have now become an essential representation of digitized scenes. Recent systems are able to capture several hundreds of millions of points in a single acquisition. As multiple acquisitions are necessary to capture the geometry of large-scale scenes, a historical site for example, we obtain massive point clouds, i.e., composed of billions of points. In this thesis, we are interested in the structuration and manipulation of point clouds from acquisitions generated by terrestrial LiDARs. From the structure of each acquisition, graphs, each representing the local connectivity of the digitized surface, are constructed. Created graphs are then linked together to obtain a global representation of the captured surface. We show that this structure is particularly adapted to the manipulation of the underlying surface of massive point clouds, even on computers with limited memory. Especially, we show that this structure allow to deal with two problems specific to that kind of data. A first one linked to the resampling of point clouds, by generating distributions of good quality in terms of blue noise thanks to a Poisson disk sampling algorithm. Another one connected to the construction of centroidal Voronoi tessellations, allowing to enhance the quality of generated distributions and to reconstruct triangular meshes
3
Baudin, Alexis. "Cliques statiques et temporelles : algorithmes d'énumération et de détection de communautés." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS609.
Full textAbstract:
Les graphes sont des objets mathématiques qui permettent de modéliser des interactions ou connexions entre entités de types variés. Un graphe peut représenter par exemple un réseau social qui connecte les utilisateurs entre eux, un réseau de transport comme le métro où les stations sont connectées entre elles, ou encore un cerveau avec les milliards de neurones en interaction qu'il contient. Depuis quelques années, la forte dynamicité de ces structures a été mise en évidence, ainsi que l'importance de prendre en compte l'évolution temporelle de ces réseaux pour en comprendre le fonctionnement. Alors que de nombreux concepts et algorithmes ont été développés sur les graphes pour décrire des structures de réseaux statiques, il reste encore beaucoup à faire pour formaliser et développer des algorithmes pertinents pour décrire la dynamique des réseaux réels. Cette thèse vise à mieux comprendre comment sont structurés les graphes massifs qui sont issus du monde réel et à développer des outils pour étendre notre compréhension à des structures évoluant dans le temps. Il a été montré que ces graphes ont des propriétés particulières, qui les distinguent des graphes théoriques ou tirés aléatoirement. Exploiter ces propriétés permet alors de concevoir des algorithmes pour résoudre certains problèmes difficiles beaucoup plus rapidement sur ces instances que dans le cas général. La thèse se focalise sur les cliques, qui sont des groupes d'éléments tous connectés entre eux. Nous étudions l'énumération des cliques dans les graphes statiques et temporels et la détection de communautés qu'elles permettent de mettre en œuvre. Les communautés d'un graphe sont des ensembles de sommets tels qu'au sein d'une communauté, les sommets interagissent fortement entre eux, et peu avec le reste du graphe. Leur étude aide à comprendre les propriétés structurelles et fonctionnelles des réseaux. Nous évaluons nos algorithmes sur des graphes massifs issus du monde réel, ouvrant ainsi de nouvelles perspectives pour comprendre les interactions au sein de ces réseaux. Nous travaillons d'abord sur des graphes, sans tenir compte de la composante temporelle des interactions. Nous commençons par utiliser la méthode de détection de communautés par percolation de cliques, en mettant en évidence ses limites en mémoire, qui empêchent de l'appliquer à des graphes trop massifs. En introduisant un algorithme de résolution approchée du problème, nous dépassons cette limite. Puis, nous améliorons l'énumération des cliques maximales dans le cas des graphes particuliers dits bipartis. Ils correspondent à des interactions entre des groupes de sommets de type différent, par exemple des liens entre des personnes et du contenu consulté, la participation à des événements, etc. Ensuite, nous considérons des interactions qui ont lieu au cours du temps, grâce au formalisme des flots de liens. Nous cherchons à étendre les algorithmes présentés en première partie, pour exploiter leurs avantages dans l'étude des interactions temporelles. Nous fournissons un nouvel algorithme d'énumération des cliques maximales dans les flots de liens, beaucoup plus efficace que l'état de l'art sur des jeux de données massifs. Enfin, nous nous intéressons aux communautés dans les flots de liens par percolation de cliques, en développant une extension de la méthode utilisée sur les graphes. Les résultats montrent une amélioration significative par rapport à l'état de l'art, et nous analysons les communautés obtenues pour fournir des informations pertinentes sur l'organisation des interactions temporelles dans les flots de liens. Mon travail de thèse a permis d’apporter de nouvelles réflexions sur l’étude des réseaux massifs issus du monde réel. Cela montre l'importance d'explorer le potentiel des graphes dans un contexte réel, et pourrait contribuer à l'émergence de solutions novatrices pour les défis complexes de notre société moderneGraphs are mathematical objects used to model interactions or connections between entities of various types. A graph can represent, for example, a social network that connects users to each other, a transport network like the metro where stations are connected to each other, or a brain with the billions of interacting neurons it contains. In recent years, the dynamic nature of these structures has been highlighted, as well as the importance of taking into account the temporal evolution of these networks to understand their functioning. While many concepts and algorithms have been developed on graphs to describe static network structures, much remains to be done to formalize and develop relevant algorithms to describe the dynamics of real networks. This thesis aims to better understand how massive graphs are structured in the real world, and to develop tools to extend our understanding to structures that evolve over time. It has been shown that these graphs have particular properties, which distinguish them from theoretical or randomly drawn graphs. Exploiting these properties then enables the design of algorithms to solve certain difficult problems much more quickly on these instances than in the general case. My PhD thesis focuses on cliques, which are groups of elements that are all connected to each other. We study the enumeration of cliques in static and temporal graphs and the detection of communities they enable. The communities of a graph are sets of vertices such that, within a community, the vertices interact strongly with each other, and little with the rest of the graph. Their study helps to understand the structural and functional properties of networks. We are evaluating our algorithms on massive real-world graphs, opening up new perspectives for understanding interactions within these networks. We first work on graphs, without taking into account the temporal component of interactions. We begin by using the clique percolation method of community detection, highlighting its limitations in memory, which prevent it from being applied to graphs that are too massive. By introducing an approximate problem-solving algorithm, we overcome this limitation. Next, we improve the enumeration of maximal cliques in the case of bipartite graphs. These correspond to interactions between groups of vertices of different types, e.g. links between people and viewed content, participation in events, etc. Next, we consider interactions that take place over time, using the link stream formalism. We seek to extend the algorithms presented in the first part, to exploit their advantages in the study of temporal interactions. We provide a new algorithm for enumerating maximal cliques in link streams, which is much more efficient than the state-of-the-art on massive datasets. Finally, we focus on communities in link streams by clique percolation, developing an extension of the method used on graphs. The results show a significant improvement over the state of the art, and we analyze the communities obtained to provide relevant information on the organization of temporal interactions in link streams. My PhD work has provided new insights into the study of massive real-world networks. This shows the importance of exploring the potential of graphs in a real-world context, and could contribute to the emergence of innovative solutions for the complex challenges of our modern society
4
Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.
Full textAbstract:
Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performancesGraphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances
5
Hernández, Rivas Cecilia Paola. "Managing massive graphs." Tesis, Universidad de Chile, 2014. http://repositorio.uchile.cl/handle/2250/131839.
Full textAbstract:
Doctora en Ciencias, Mención ComputaciónCon la popularidad de la Web y, mas recientemente, el amplio uso de las redes sociales, la necesidad de procesar y encontrar información en grafos muy grandes impone varios desafíos: Cómo procesar grafos muy grandes e cientemente, dado que probablemente son muy grandes para la memoria disponible, o incluso si la memoria es su ciente, realizar un paso sobre el grafo es todavía caro computacionalmente? Cómo almacenar esos grafos e cientemente, para ser archivados, o para ejecutar algoritmos de grafos? Cómo descubrir información relevante tal como componentes densos, comunidades, u otras estructuras? Se han propuesto tres enfoques para manejar grafos grandes. El primero es usar formatos de grafos comprimidos que permiten consultas de navegación básicas directamentee sobre la estructura comprimida, sin la necesidad de descompresión. Esto permite simular cualquier algoritmo de grafo en memoria principal usando mucho menos espacio que la representación plana. Una segunda línea de investigación se focaliza en usar modelos de stream o semi- stream de datos de manera de procesar secuencialmente, idealmente en un paso sobre el disco, usando una cantidad limitada de memoria principal. La tercera línea es el uso de sistemas distribuidos y paralelos donde la memoria es agregada sobre múltiples unidades de procesamiento para procesar el grafo en paralelo. En esta tesis presentamos varios enfoques para manejar grafos grandes (con arcos sin etiquetas) considerando los tres enfoques. Primero, buscamos por patrones que aparecen en grafos de la Web y redes sociales los que podemos representar en forma compacta, en particular mostramos como generalizar algoritmos para encontrar cliques o bicliques para encontrar sub-estructuras densas que comprimen ambas. Segundo, basado en estos subgrafos densos, proponemos esquemas comprimidos que soportan consultas de vecinos directos y reversos, así como otras consultas mas complejas sobre subgrafos densos. Algunas de las contribuciones combinan técnicas del estado del arte mientras otras incluyen representaciones comprimidas novedosas basadas en estructuras de datos compactas. Encontrar subgrafos densos es una tarea que consume tiempo y espacio, así que proporcionamos algoritmos de streaming and algoritmos de memoria externa para descubrir subgrafos densos, asi como también algoritmos distribuidos para construir las estructuras básicas que usamos para las representaciones comprimidas.
6
Gillet, Noel. "Optimisation de requêtes sur des données massives dans un environnement distribué." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0553/document.
Full textAbstract:
Les systèmes de stockage distribués sont massivement utilisés dans le contexte actuel des grandes masses de données. En plus de gérer le stockage de ces données, ces systèmes doivent répondre à une quantité toujours plus importante de requêtes émises par des clients distants afin d’effectuer de la fouille de données ou encore de la visualisation. Une problématique majeure dans ce contexte consiste à répartir efficacement les requêtes entre les différents noeuds qui composent ces systèmes afin de minimiser le temps de traitement des requêtes ( temps maximum et en moyenne d’une requête, temps total de traitement pour toutes les requêtes...). Dans cette thèse nous nous intéressons au problème d’allocation de requêtes dans un environnement distribué. On considère que les données sont répliquées et que les requêtes sont traitées par les noeuds stockant une copie de la donnée concernée. Dans un premier temps, des solutions algorithmiques quasi-optimales sont proposées lorsque les communications entre les différents noeuds du système se font de manière asynchrone. Le cas où certains noeuds du système peuvent être en panne est également considéré. Dans un deuxième temps, nous nous intéressons à l’impact de la réplication des données sur le traitement des requêtes. En particulier, un algorithme qui adapte la réplication des données en fonction de la demande est proposé. Cet algorithme couplé à nos algorithmes d’allocation permet de garantir une répartition des requêtes proche de l’idéal pour toute distribution de requêtes. Enfin, nous nous intéressons à l’impact de la réplication quand les requêtes arrivent en flux sur le système. Nous procédons à une évaluation expérimentale sur la base de données distribuées Apache Cassandra. Les expériences réalisées confirment l’intérêt de la réplication et de nos algorithmes d’allocation vis-à-vis des solutions présentes par défaut dans ce systèmeDistributed data store are massively used in the actual context of Big Data. In addition to provide data management features, those systems have to deal with an increasing amount of queries sent by distant users in order to process data mining or data visualization operations. One of the main challenge is to evenly distribute the workload of queries between the nodes which compose these system in order to minimize the treatment time. In this thesis, we tackle the problem of query allocation in a distributed environment. We consider that data are replicated and a query can be handle only by a node storing the concerning data. First, near-optimal algorithmic proposals are given when communications between nodes are asynchronous. We also consider that some nodes can be faulty. Second, we study more deeply the impact of data replication on the query treatement. Particularly, we present an algorithm which manage the data replication based on the demand on these data. Combined with our allocation algorithm, we guaranty a near-optimal allocation. Finally, we focus on the impact of data replication when queries are received as a stream by the system. We make an experimental evaluation using the distributed database Apache Cassandra. The experiments confirm the interest of our algorithmic proposals to improve the query treatement compared to the native allocation scheme in Cassandra
7
Wang, Guan. "STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS." Kent State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649.
Full text
8
Habi, Abdelmalek. "Search and Aggregation in Big Graphs." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1259/document.
Full textAbstract:
Ces dernières années ont connu un regain d'intérêt pour l'utilisation des graphes comme moyen fiable de représentation et de modélisation des données, et ce, dans divers domaines de l'informatique. En particulier, pour les grandes masses de données, les graphes apparaissent comme une alternative prometteuse aux bases de données relationnelles. Plus particulièrement, le recherche de sous-graphes s'avère être une tâche cruciale pour explorer ces grands jeux de données. Dans cette thèse, nous étudions deux problématiques principales. Dans un premier temps, nous abordons le problème de la détection de motifs dans les grands graphes. Ce problème vise à rechercher les k-meilleures correspondances (top-k) d'un graphe motif dans un graphe de données. Pour cette problématique, nous introduisons un nouveau modèle de détection de motifs de graphe nommé la Simulation Relaxée de Graphe (RGS), qui permet d’identifier des correspondances de graphes avec un certain écart (structurel) et ainsi éviter le problème de réponse vide. Ensuite, nous formalisons et étudions le problème de la recherche des k-meilleures réponses suivant deux critères, la pertinence (la meilleure similarité entre le motif et les réponses) et la diversité (la dissimilarité entre les réponses). Nous considérons également le problème des k-meilleures correspondances diversifiées et nous proposons une fonction de diversification pour équilibrer la pertinence et la diversité. En outre, nous développons des algorithmes efficaces basés sur des stratégies d’optimisation en respectant le modèle proposé. Notre approche est efficiente en terme de temps d’exécution et flexible en terme d'applicabilité. L’analyse de la complexité des algorithmes et les expérimentations menées sur des jeux de données réelles montrent l’efficacité des approches proposées. Dans un second temps, nous abordons le problème de recherche agrégative dans des documents XML. Pour un arbre requête, l'objectif est de trouver des motifs correspondants dans un ou plusieurs documents XML et de les agréger dans un seul agrégat. Dans un premier temps nous présentons la motivation derrière ce paradigme de recherche agrégative et nous expliquons les gains potentiels par rapport aux méthodes classiques de requêtage. Ensuite nous proposons une nouvelle approche qui a pour but de construire, dans la mesure du possible, une réponse cohérente et plus complète en agrégeant plusieurs résultats provenant de plusieurs sources de données. Les expérimentations réalisées sur plusieurs ensembles de données réelles montrent l’efficacité de cette approche en termes de pertinence et de qualité de résultatRecent years have witnessed a growing renewed interest in the use of graphs as a reliable means for representing and modeling data. Thereby, graphs enable to ensure efficiency in various fields of computer science, especially for massive data where graphs arise as a promising alternative to relational databases for big data modeling. In this regard, querying data graph proves to be a crucial task to explore the knowledge in these datasets. In this dissertation, we investigate two main problems. In the first part we address the problem of detecting patterns in larger graphs, called the top-k graph pattern matching problem. We introduce a new graph pattern matching model named Relaxed Graph Simulation (RGS), to identify significant matches and to avoid the empty-set answer problem. We formalize and study the top-k matching problem based on two classes of functions, relevance and diversity, for ranking the matches according to the RGS model. We also consider the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Moreover, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the proposed model. The proposed approach is optimal in terms of search time and flexible in terms of applicability. The analyze of the time complexity of the proposed algorithms and the extensive experiments on real-life datasets demonstrate both the effectiveness and the efficiency of these approaches. In the second part, we tackle the problem of graph querying using aggregated search paradigm. We consider this problem for particular types of graphs that are trees, and we deal with the query processing in XML documents. Firstly, we give the motivation behind the use of such a paradigm, and we explain the potential benefits compared to traditional querying approaches. Furthermore, we propose a new method for aggregated tree search, based on approximate tree matching algorithm on several tree fragments, that aims to build, the extent possible, a coherent and complete answer by combining several results. The proposed solutions are shown to be efficient in terms of relevance and quality on different real-life datasets
9
Jiang, Jiaxin. "Efficient frameworks for keyword search on massive graphs." HKBU Institutional Repository, 2020. https://repository.hkbu.edu.hk/etd_oa/806.
Full textAbstract:
Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques
10
Lu, Linyuan Lincoln. "Probabilistic methods in massive graphs and internet computing /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2002. http://wwwlib.umi.com/cr/ucsd/fullcit?p3061653.
Full textBooks on the topic "Graphe massifs"
1
Bader, David A. Massive Graph Analytics. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707.
Full text
2
Caproni, Giorgio. Il Girasole. Edited by Giada Baragli. Florence: Firenze University Press, 2017. http://dx.doi.org/10.36253/978-88-6453-495-4.
Full textAbstract:
«Apriamo a caso il libro». È così che si eclissava tra il ’72 e il ’75 la voce-guida di Caproni per lasciare ad altri il microfono della trasmissione radiofonica «Il girasole». Una rubrica destinata alla divulgazione, trasmessa nelle ore di massimo ascolto del programma nazionale, con lo scopo di offrire ad un pubblico largo e diversificato una sorta di ‘sussidiario’ letterario che desse ai colti il piacere della rilettura e ai più giovani e sprovveduti quello della scoperta. Un grande poeta, Giorgio Caproni, aveva il compito di scegliere i passi da testi di ogni tempo e paese (poesia, narrativa, teatro…) e di collegarli tra loro con poche parole di presentazione in grado di ricreare un ambiente, un’epoca, insomma quanto sta intorno all’opera d’arte e la rende per tutti comprensibile e umana. È questa singolare avventura che – perduti/distrutti i materiali radiofonici – riusciamo infine a conoscere grazie all’attenta cura di Giada Baragli, che da copioni spesso lacunosi ha ricostruito il florilegio di un centinaio di brani che non solo offrono una preziosa antologia comparata della letteratura, ma ci parlano delle predilezioni e delle letture di uno straordinario, indimenticabile autore che ha anche collaborato con la radio.
3
Bader, David A. Massive Graph Analytics. Taylor & Francis Group, 2022.
Find full text
4
Bader, David A. Massive Graph Analytics. CRC Press LLC, 2022.
Find full text
5
Bader, David A. Massive Graph Analytics. Taylor & Francis Group, 2022.
Find full text
6
Massive Graph Analytics. Taylor & Francis Group, 2022.
Find full text
7
Bader, David A. Massive Graph Analytics. Taylor & Francis Group, 2022.
Find full text
8
Staff, Smart Books Inc, and Eric Char. Massive Graph Paper Book. Independently Published, 2018.
Find full text
9
Massive - Ragnarok. Dark Horse Comics, 2015.
Find full text
10
Vivian, Aaron. Massive Graph Book: 500 Pages of Assorted Graph Paper for Drawing. Independently Published, 2021.
Find full textBook chapters on the topic "Graphe massifs"
1
Slota, George M., Sivasankaran Rajamanickam, and Kamesh Madduri. "Multicore Algorithms for Graph Connectivity Problems." In Massive Graph Analytics, 63–84. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-5.
Full text
2
Fender, Alex, Brad Rees, and Joe Eaton. "RAPIDS cuGraph." In Massive Graph Analytics, 483–93. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-22.
Full text
3
Penschuck, Manuel, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, and Christian Schulz. "Recent Advances in Scalable Network Generation1." In Massive Graph Analytics, 333–76. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-16.
Full text
4
Erb, Stephan, Moritz Kobitzsch, Lawrence Mandow, and Peter Sanders. "Multi-Objective Shortest Paths." In Massive Graph Analytics, 35–59. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-3.
Full text
5
Hasenplaugh, William, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. "Ordering Heuristics for Parallel Graph Coloring." In Massive Graph Analytics, 193–221. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-11.
Full text
6
Angriman, Eugenio, Patrick Bisenius, Elisabetta Bergamini, and Henning Meyerhenke. "Computing Top-k Closeness Centrality in Fully Dynamic Graphs." In Massive Graph Analytics, 161–92. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-10.
Full text
7
Srivastava, Ajitesh, Charalampos Chelmis, and Viktor K. Prasanna. "Computational Models for Cascades in Massive Graphs." In Massive Graph Analytics, 377–95. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-17.
Full text
8
Du, Zhihui, Oliver Alvarado Rodriguez, Joseph Patchett, and David A. Bader. "Interactive Graph Analytics at Scale in Arkouda." In Massive Graph Analytics, 549–89. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-26.
Full text
9
Sanders, Geoffrey, Roger Pearce, Benjamin W. Priest, and Trevor Steil. "Massive-Scale Distributed Triangle Computation and Applications." In Massive Graph Analytics, 127–58. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-8.
Full text
10
Leiserson, Charles E., and Tao B. Schardl. "A Work-Efficient Parallel Breadth-First Search Algorithm (or How To Cope With the Nondeterminism of Reducers)." In Massive Graph Analytics, 3–33. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9781003033707-2.
Full textConference papers on the topic "Graphe massifs"
1
Aiello, William, Fan Chung, and Linyuan Lu. "A random graph model for massive graphs." In the thirty-second annual ACM symposium. New York, New York, USA: ACM Press, 2000. http://dx.doi.org/10.1145/335305.335326.
Full text
2
Gao, Jian, Jiejiang Chen, Minghao Yin, Rong Chen, and Yiyuan Wang. "An Exact Algorithm for Maximum k-Plexes in Massive Graphs." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/201.
Full textAbstract:
The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.
3
Jiang, Hua, Dongming Zhu, Zhichao Xie, Shaowen Yao, and Zhang-Hua Fu. "A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/233.
Full textAbstract:
Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing exact algorithms usually implement a branch-and-bound approach that requires a tight upper bound to reduce the search space. In this paper, we propose a new upper bound for MKP, which is a partitioning of the candidate vertex set with respect to the constructing solution. We implement a new branch-and-bound algorithm that employs the upper bound to reduce the number of branches. Experimental results show that the upper bound is very effective in reducing the search space. The new algorithm outperforms the state-of-the-art algorithms significantly on real-world massive graphs, DIMACS graphs and random graphs.
4
Hu, Xiaocheng, Yufei Tao, and Chin-Wan Chung. "Massive graph triangulation." In the 2013 international conference. New York, New York, USA: ACM Press, 2013. http://dx.doi.org/10.1145/2463676.2463704.
Full text
5
Wang, Zhengren, Yi Zhou, Chunyu Luo, and Mingyu Xiao. "A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/627.
Full textAbstract:
Given a graph, the k-plex is a vertex set in which each vertex is not adjacent to at most k-1 other vertices in the set. The maximum k-plex problem, which asks for the largest k-plex from a given graph, is an important but computationally challenging problem in applications like graph search and community detection. So far, there is a number of empirical algorithms without sufficient theoretical explanations on the efficiency. We try to bridge this gap by defining a novel parameter of the input instance, g_k(G), the gap between the degeneracy bound and the size of maximum k-plex in the given graph, and presenting an exact algorithm parameterized by g_k(G). In other words, we design an algorithm with running time polynomial in the size of input graph and exponential in g_k(G) where k is a constant. Usually, g_k(G) is small and bounded by O(log(|V|)) in real-world graphs, indicating that the algorithm runs in polynomial time. We also carry out massive experiments and show that the algorithm is competitive with the state-of-the-art solvers. Additionally, for large k values such as 15 and 20, our algorithm has superior performance over existing algorithms.
6
Eberhart, Aaron, Peter Haase, and Wolfgang Schell. "metaphactory for Massive Graphs." In ICPE '23: ACM/SPEC International Conference on Performance Engineering. New York, NY, USA: ACM, 2023. http://dx.doi.org/10.1145/3578245.3585330.
Full text
7
King, Valerie, Alex Thomo, and Quinton Yong. "Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/240.
Full textAbstract:
The problem of finding the degeneracy of a graph is a subproblem of the k-core decomposition problem. In this paper, we present a (1 + epsilon)-approximate solution to the degeneracy problem which runs in O(n log n) time, sublinear in the input size for dense graphs, by sampling a small number of neighbors adjacent to high degree nodes. This improves upon the previous work on sublinear approximate degeneracy, which implies a (4 + epsilon)-approximate ~O(n) solution. Our algorithm can be extended to an approximate O(n log n) time solution to the k-core decomposition problem. We also explore the use of our approximate algorithm as a technique for speeding up exact degeneracy computation. We prove theoretical guarantees of our algorithm and provide optimizations, which improve the running time of our algorithm in practice. Experiments on massive real-world web graphs show that our algorithm performs significantly faster than previous methods for computing degeneracy.
8
Wang, Yiyuan, Shaowei Cai, Jiejiang Chen, and Minghao Yin. "A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/210.
Full textAbstract:
The minimum weight dominating set (MWDS) problem is NP-hard and also important in many applications. Recent heuristic MWDS algorithms can hardly solve massive real world graphs effectively. In this paper, we design a fast local search algorithm called FastMWDS for the MWDS problem, which aims to obtain a good solution on massive graphs within a short time. In this novel local search framework, we propose two ideas to make it effective. Firstly, we design a new fast construction procedure with four reduction rules to cut down the size of massive graphs. Secondly, we propose the three-valued two-level configuration checking strategy to improve local search, which is interestingly a variant of configuration checking (CC) with two levels and multiple values. Experiment results on a broad range of massive real world graphs show that FastMWDS finds much better solutions than state of the art MWDS algorithms.
9
Aiello, W., Fan Chung, and Linyuan Lu. "Random evolution in massive graphs." In Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001. http://dx.doi.org/10.1109/sfcs.2001.959927.
Full text
10
Tabassum, Shazia, and João Gama. "Sampling massive streaming call graphs." In SAC 2016: Symposium on Applied Computing. New York, NY, USA: ACM, 2016. http://dx.doi.org/10.1145/2851613.2851654.
Full textReports on the topic "Graphe massifs"
1
Wylie, Brian Neil, and Kenneth D. Moreland. Massive graph visualization : LDRD final report. Office of Scientific and Technical Information (OSTI), October 2007. http://dx.doi.org/10.2172/921736.
Full text
2
Marcus, L. F., and P. Lampietti. Interactive graphic analysis and sequence comparison of host rocks containing stratiform volcanogenic massive sulphide deposits. Natural Resources Canada/ESS/Scientific and Technical Publishing Services, 1990. http://dx.doi.org/10.4095/128083.
Full text
3
Kaffenberger, Michelle, Lant Pritchett, and Martina Viarengo. Towards a Right to Learn: Concepts and Measurement of Global Education Poverty. Research on Improving Systems of Education (RISE), December 2021. http://dx.doi.org/10.35489/bsg-rise-wp_2021/085.
Full textAbstract:
The idea that children have a “right to education” has been widely accepted since the Universal Declaration of Human Rights in 1948 (United Nations, 1948) and periodically reinforced since. The “right to education” has always, explicitly or implicitly, encompassed a “right to learn.” Measures of schooling alone, such as enrollment or grade attainment, without reference to skills, capabilities, and competencies acquired, are inadequate for defining education or education poverty. Because of education’s cumulative and dynamic nature, education poverty needs an “early” standard (e.g., Grade 3 or 4 or age 8 or 10) and a “late” standard (e.g., Grade 10 or 12 or ages 15 and older). Further, as with all international poverty definitions, there needs to be a low, extreme standard, which is found almost exclusively in low- and middle-income countries and can inform prioritization and action, and a higher “global” standard, against which even some children in high income countries would be considered education poor but which is considered a reasonable aspiration for all children. As assessed against any proposed standard, we show there is a massive learning crisis: students spend many years in school and yet do not reach an early standard of mastery of foundational skills nor do they reach any reasonable global minimum standard by the time they emerge from school. The overwhelming obstacle to addressing education poverty today is not enrollment/grade attainment nor inequality in learning achievement, but the fact that the typical learning profile is just too shallow for children to reach minimum standards.
4
Pacheco-Ojeda, Luis, Carolina Sáenz-Gómez, Stalin Cañizares-Quisiguiña, Tatiana Borja-Herrera, Juan Carlos Vallejo-Garzón, and Sergio Poveda. Function Sparing Conservative Approach of a Low-Grade Chondrosarcoma of the Larynx: Case Report and Literature Review. Science Repository, March 2024. http://dx.doi.org/10.31487/j.scr.2024.01.04.
Full textAbstract:
Background: Laryngeal cancer is relatively uncommon in Ecuador. Usually epithelial in origin, the most frequent histological type is squamous cell carcinoma. The most common mesenchymal tumor is chondrosarcoma. Most laryngeal chondrosarcomas are treated with total laryngectomy, but a conservative function sparing resection is recommended in low-grade limited tumors. Case Report: In a 68-year-old female nonsmoker patient, a small tumor was found in the posterior left aspect of the cricoid cartilage in a computed tomography (CT) performed immediately after an unexpected difficulty to pass the endotracheal tube for a thoracoscopic biopsy of 4 cm tumor of the left lung, in another hospital. The patient underwent, then, an initial tracheostomy, a total thyroidectomy for a goiter and a biopsy of the tumor of the cricoid cartilage whose pathological study was inconclusive. One month later, a low-grade neuroendocrine pulmonary tumor was completed resected. Two years later, a CT scan showed the cricoid lesion with the same characteristics. At endoscopic video laryngoscopy, two subglottic masses that narrowed the airway in approximately 60% of the normal caliber, were observed located at the posterior and left walls. An intraluminal resection was performed through a transcricoid anterior approach. The pathological diagnosis was a low-grade chondrosarcoma. Tracheal decannulation was performed one month later. At an endoscopic video laryngoscopy performed six months post-operatively, the tracheal caliber and mucosa were normal. The patient remained with normal voice and breathing. Conclusion: We report the second case of chondrosarcoma of the larynx in our country, treated by a conservative approach.
5
Berkhout, Emilie, Goldy Dharmawan, Amanda Beatty, Daniel Suryadarma, and Menno Pradhan. Who Benefits and Loses from Large Changes to Student Composition? Assessing Impacts of Lowering School Admissions Standards in Indonesia. Research on Improving Systems of Education (RISE), April 2022. http://dx.doi.org/10.35489/bsg-risewp_2022/094.
Full textAbstract:
We study the effects of an admission policy change that caused a massive shift in student composition in public and private junior secondary schools in Yogyakarta, Indonesia. In 2018, the primary criterion for admission into Yogyakarta’s 16 preferred, free public schools (grades 7-9) changed from a grade 6 exam score ranking to a neighborhood-to-school distance ranking. This policy change resulted in a decline in average grade 6 scores in public schools by 0.4 standard deviations (s.d.) and a 0.4 s.d. increase in private schools. We assessed learning impacts caused by the changed student composition by comparing two otherwise similar cohorts of students admitted before and after the policy change. Average grade 8 test scores across math and Indonesian declined by 0.08 s.d. (not significant). To understand which students throughout the education system gained and lost in terms of learning, we simulated public school access under the 2018 policy and its predecessor for both cohorts. In public schools, teachers attempted to adapt lessons to lower-scoring students by changing teaching approaches and tracking students. These responses and/or exposure to different peers negatively affected learning for students predicted to have access to public schools under both policies (-0.13 s.d., significant at the 10 percent level) and aided students with predicted public school access under the new policy slightly (0.12 s.d., not significant). These results are in contrast to existing literature which finds little or no impact from shifts in student composition on incumbent students’ learning. In private schools, we found no such adaptations and no effects on predicted incumbent students. However, students predicted to enter private schools under the new policy saw large negative effects (-0.24 s.d., significant), due to lower school quality and/or peer effects. Our results demonstrate that effects from high-performing, selective schools can be highly heterogenous and influenced by student composition.
6
Berkhout, Emilie, Goldy Dharmawan, Amanda Beatty, Daniel Suryadarma, and Menno Pradhan. Who Benefits and Loses from Large Changes to Student Composition? Assessing Impacts of Lowering School Admissions Standards in Indonesia. Research on Improving Systems of Education (RISE), April 2022. http://dx.doi.org/10.35489/bsg-risewp_2022/094.
Full textAbstract:
We study the effects of an admission policy change that caused a massive shift in student composition in public and private junior secondary schools in Yogyakarta, Indonesia. In 2018, the primary criterion for admission into Yogyakarta’s 16 preferred, free public schools (grades 7-9) changed from a grade 6 exam score ranking to a neighborhood-to-school distance ranking. This policy change resulted in a decline in average grade 6 scores in public schools by 0.4 standard deviations (s.d.) and a 0.4 s.d. increase in private schools. We assessed learning impacts caused by the changed student composition by comparing two otherwise similar cohorts of students admitted before and after the policy change. Average grade 8 test scores across math and Indonesian declined by 0.08 s.d. (not significant). To understand which students throughout the education system gained and lost in terms of learning, we simulated public school access under the 2018 policy and its predecessor for both cohorts. In public schools, teachers attempted to adapt lessons to lower-scoring students by changing teaching approaches and tracking students. These responses and/or exposure to different peers negatively affected learning for students predicted to have access to public schools under both policies (-0.13 s.d., significant at the 10 percent level) and aided students with predicted public school access under the new policy slightly (0.12 s.d., not significant). These results are in contrast to existing literature which finds little or no impact from shifts in student composition on incumbent students’ learning. In private schools, we found no such adaptations and no effects on predicted incumbent students. However, students predicted to enter private schools under the new policy saw large negative effects (-0.24 s.d., significant), due to lower school quality and/or peer effects. Our results demonstrate that effects from high-performing, selective schools can be highly heterogenous and influenced by student composition.
7
Gadd, M. G., J. M. Peter, and D. Layton-Matthews. Genesis of hyper-enriched black shale Ni-Mo-Zn-Pt-Pd-Re mineralization in the northern Canadian Cordillera. Natural Resources Canada/CMSS/Information Management, 2022. http://dx.doi.org/10.4095/328013.
Full textAbstract:
Polymetallic (Ni-Mo-Zn-Pt-Pd-Au-Re) hyper-enriched black shales in the northern Canadian Cordillera consist of thin, semi-massive sulfides interbedded with black shale. We studied HEBS deposits at Nick, Peel River, Monster River, and Moss in northern Yukon, and at a single locality underlying the Cardiac Creek Pb-Zn-Ag deposit in northeastern British Columbia. High-grade mineralization contains up to 7.4 weight per cent Ni, 2.7 weight per cent Zn, 0.38 weight per cent Mo, 400 ppb Pt, 250 ppb Pd, 160 ppb Au, and 58.5 ppm Re. Sulfide mineralization formed during syngenesis to later diagenesis. Analyses by LA-ICP-MS indicate that pyrite is the principal host of platinum-group elements, Au, and Re. Mineralization and sedimentation were coeval based on the overlap between Re-Os geochronology of HEBS at Nick and Peel River (390.7 ± 5.1 and 387.3 ± 4.4 Ma, respectively) and conodont biostratigraphic ages of sedimentary host rocks. Bulk S isotope composition of HEBS is uniformly negative, indicating that bacterial reduction of seawater sulfate generated sulfur to precipitate sulfide minerals. The initial Os ratios at Peel River (0.25 ± 0.07) and Nick (0.32 ± 0.20) overlap with Middle Devonian seawater, suggesting that elemental enrichment was derived from seawater.
8
Mawassi, Munir, and Valerian V. Dolja. Role of the viral AlkB homologs in RNA repair. United States Department of Agriculture, June 2014. http://dx.doi.org/10.32747/2014.7594396.bard.
Full textAbstract:
AlkB proteins that repair DNA via reversing methylation damage are conserved in a broad range of prokaryotes and eukaryotes including plants. Surprisingly, AlkB-domains were discovered in the genomes of numerous plant positive-strand RNA viruses, majority of which belong to the family Flexiviridae. The major goal of this research was to reveal the AlkB functions in the viral infection cycle using a range of complementary genetic and biochemical approaches. Our hypotheses was that AlkB is required for efficient replication and genetic stability of viral RNA genomes The major objectives of the research were to identify the functions of GVA AlkB domain throughout the virus infection cycle in N. benthamiana and grapevine, to investigate possible RNA silencing suppression activity of the viral AlkBs, and to characterize the RNA demethylation activity of the mutated GVA AlkBs in vitro and in vivo to determine methylation status of the viral RNA. Over the duration of project, we have made a very substantial progress with the first two objectives. Because of the extreme low titer of the virus particles in plants infected with the AlkB mutant viruses, we were unable to analyze RNA demethylation activity and therefore had to abandon third objective. The major achievements with our objectives were demonstration of the AlkB function in virus spread and accumulation in both experimental and natural hosts of GVA, discovery of the functional cooperation and physical interaction between AlkB and p10 AlkB in suppression of plant RNA silencing response, developing a powerful virus vector technology for grapevine using GLRaV-2-derived vectors for functional genomics and pathogen control in grapevine, and in addition we used massive parallel sequencing of siRNAs to conduct comparative analysis of the siRNA populations in grape plants infected with AlkB-containing GLRaV-3 versus GLRaV-2 that does not encode AlkB. This analysis revealed dramatically reduced levels of virus-specific siRNAs in plants infected with GLRaV-3 compared to that in GLRaV-2 infection implicating AlkB in suppression of siRNA formation. We are pleased to report that BARD funding resulted in 5 publications directly supported by BARD, one US patent, and 9 more publications also relevant to project. Moreover, two joint manuscripts that summarize work on GVA AlkB (led by Israeli PI) and on viral siRNAs in grapevine (led by US PI in collaboration with University of Basel) are in preparation.
9
Fontecave, Marc, and Candel Sébastien. Quelles perspectives énergétiques pour la biomasse ? Académie des sciences, January 2024. http://dx.doi.org/10.62686/1.
Full textAbstract:
Le débat public concernant l’avenir du mix énergétique français à l’horizon 2050 a longtemps été réduit à la seule considération de son volet électrique, dans une opposition entre énergie nucléaire et énergies renouvelables (EnR). Pourtant, la part non-électrique de notre consommation énergétique constitue clairement aujourd’hui un des principaux défis de la transition climatique et énergétique. Actuellement issue du pétrole, du gaz et du charbon, elle constitue l’angle mort des divers scénarios énergétiques disponibles, alors qu’elle restera encore indispensable, notamment dans le secteur de la mobilité et de la production de chaleur. Le Comité de prospective en énergie (CPE) de l’Académie des sciences examine ici les ressources énergétiques et carbonées pouvant être tirées de la biomasse, qui présente des atouts certains en permettant le stockage de l’énergie sous forme de biogaz ou de biocarburants, et les perspectives raisonnables offertes par celles-ci dans le mix énergétique national à l’horizon 2050. Le présent rapport se focalise sur les aspects scientifiques et technologiques, sans occulter certaines considérations environnementales, économiques, sociales, et de souveraineté nationale, abordés à la lumière de la littérature disponible et de l’audition d’experts des divers domaines considérés. Après avoir défini la notion de biomasse dans sa diversité, le rapport décrit les différentes bioénergies possibles et leurs limites. Les utilisations actuelles de la biomasse en France sont évaluées et comparées aux perspectives envisagées à l’horizon 2050 au regard du potentiel réellement mobilisable, pour lequel il existe une grande variation dans les estimations proposées, et des technologies nécessaires à sa transformation, qui restent, pour la plupart, coûteuses et de faible maturité. Ainsi, cette analyse montre notamment que le besoin d’énergie non-électrique, tel qu’il est défini dans le scénario de référence fourni par Réseau de transport d’électricité (RTE), sera difficile – pour ne pas dire impossible - à atteindre avec la seule biomasse produite en France : le bouclage énergétique 2050 passera nécessairement par un maintien d’importations de gaz naturel et par de nouvelles importations de biomasse et/ou de bioénergie introduisant des dépendances nouvelles et exportant les risques associés à leur utilisation massive. Le rapport rappelle que la bioénergie reste l’énergie la moins favorable en termes d’empreinte spatiale et que la biomasse a, sur toute la chaîne des valeurs, un faible retour énergétique. Sa plus grande mobilisation, qui ne devra pas se faire au détriment de la sécurité alimentaire humaine et animale, ni au détriment des éco-services rendus par la biosphère, aura des impacts environnementaux certains qu’il faudrait estimer avec rigueur. Enfin, le remplacement de la pétrochimie industrielle par une nouvelle « carbochimie biosourcée » va nécessiter des efforts considérables d’adaptation des procédés et de recherche et développement dans le domaine de la catalyse, de la chimie de synthèse et des biotechnologies. Ces conclusions conduisent le CPE à formuler des recommandations concernant : 1.La nécessaire amélioration de la concertation entre les divers organismes et agences pour aboutir à une estimation rigoureuse et convergente des ressources potentielles, 2.La réalisation de bilans carbone des diverses filières et d’analyses en termes de retour énergétique des investissements envisagés, pour s’assurer de la soutenabilité et du gain en carbone qui ne sont pas acquis pour le moment, 3.Le soutien au déploiement de la recherche et développement des filières de biocarburants de seconde génération pour accroitre leur maturité industrielle, 4.La poursuite du développement d’une chimie organique de synthèse biosourcée, 5.La priorité à établir dans l’utilisation de la biomasse pour les usages qui ne pourront être décarbonés par l’électricité, passant par une politique publique permettant de résoudre les conflits d’usages, 6.La nécessité de concertation des politiques énergétique et agroalimentaire de notre pays.