the proceedings contain 9 papers. the special focus in this conference is on algorithms and models for the webgraph. the topics include: Almost exact recovery in label spreading;strongly n-e.c. graphs and independent...
ISBN:
(纸本)9783030250690
the proceedings contain 9 papers. the special focus in this conference is on algorithms and models for the webgraph. the topics include: Almost exact recovery in label spreading;strongly n-e.c. graphs and independent distinguishing labellings;the Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random graphs;estimating the parameters of the Waxman random graph;understanding the effectiveness of data reduction in public transportation networks;a spatial small-world graph arising from activity-based reinforcement;***—novel software framework for modelling and analysis of hypergraphs.
A knowledge graph (KG) consists of numerous triples, in which each triple, i.e., (head entity, relation, tail entity), denotes a real-world assertion. Many large-scale KGs have been developed, e.g., general-purpose KG...
详细信息
ISBN:
(纸本)9781450394079
A knowledge graph (KG) consists of numerous triples, in which each triple, i.e., (head entity, relation, tail entity), denotes a real-world assertion. Many large-scale KGs have been developed, e.g., general-purpose KGs Freebase and YAGO. Also, lots of domain-specific KGs are emerging, e.g., COVID-19 KGs, biomedical KGs, and agricultural KGs. By embedding KGs into low-dimensional vectors, i.e., representations of entities and relations, we could integrate KGs into machine learning models and enhance the performance of many prediction tasks, including search, recommendations, and question answering. During the construction, refinement, embedding, and application of KGs, a variety of KG learning algorithms have been developed to handle challenges in various real-world scenarios. Moreover, graph neural networks have also brought new opportunities to KG learning. this workshop aims to engage with active researchers from KG communities, recommendation communities, natural language processing communities, and other communities, and deliver state-of-the-art research insights into the core challenges in KG learning.
Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, r...
详细信息
ISBN:
(数字)9783030250706
ISBN:
(纸本)9783030250690;9783030250706
Given a public transportation network of stations and connections, we want to find a minimum subset of stations such that each connection runs through a selected station. Although this problem is NP-hard in general, real-world instances are regularly solved almost completely by a set of simple reduction rules. To explain this behavior, we view transportation networks as hitting set instances and identify two characteristic properties, locality and heterogeneity. We then devise a randomized model to generate hitting set instances with adjustable properties. While the heterogeneity does influence the effectiveness of the reduction rules, the generated instances show that locality is the significant factor. Beyond that, we prove that the effectiveness of the reduction rules is independent of the underlying graph structure. Finally, we show that high locality is also prevalent in instances from other domains, facilitating a fast computation of minimum hitting sets.
web crawlers are used by internet search engines to gather information about the webgraph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once init...
详细信息
Modularity is designed to measure the strength of division of a network into clusters (known also as communities). Networks with high modularity have dense connections between the vertices within clusters but sparse c...
详细信息
ISBN:
(数字)9783319497877
ISBN:
(纸本)9783319497877;9783319497860
Modularity is designed to measure the strength of division of a network into clusters (known also as communities). Networks with high modularity have dense connections between the vertices within clusters but sparse connections between vertices of different clusters. As a result, modularity is often used in optimization methods for detecting community structure in networks, and so it is an important graph parameter from practical point of view. Unfortunately, many existing nonspatial models of complex networks do not generate graphs with high modularity;on the other hand, spatial models naturally create clusters. We investigate this phenomenon by considering a few examples from both sub-classes. We prove precise theoretical results for the classical model of random d-regular graphs as well as the preferential attachment model, and contrast these results withthe ones for the spatial preferential attachment (SPA) model that is a model for complex networks in which vertices are embedded in a metric space, and each vertex has a sphere of influence whose size increases if the vertex gains an in-link, and
暂无评论