Arnau Prat-Pérez

Angela Bonifati, Irena Holubová, Arnau Prat-Pérez et al.

The abundance of interconnected data has fueled the design and implementation of graph generators reproducing real-world linking properties, or gauging the effectiveness of graph algorithms, techniques and applications manipulating these data. We consider graph generation across multiple subfields, such as Semantic Web, graph databases, social networks, and community detection, along with general graphs. Despite the disparate requirements of modern graph generators throughout these communities, we analyze them under a common umbrella, reaching out the functionalities, the practical usage, and their supported operations. We argue that this classification is serving the need of providing scientists, researchers and practitioners with the right data generator at hand for their work. This survey provides a comprehensive overview of the state-of-the-art graph generators by focusing on those that are pertinent and suitable for several data-intensive tasks. Finally, we discuss open challenges and missing requirements of current graph generators along with their future extensions to new emerging fields.

Joan Guisado-Gámez, Arnau Prat-Pérez, Josep Lluís Larriba-Pey

The search for relevant information can be very frustrating for users who, unintentionally, use too general or inappropriate keywords to express their requests. To overcome this situation, query expansion techniques aim at transforming the user request by adding new terms, referred as expansion features, that better describe the real intent of the users. We propose a method that relies exclusively on relevant structures (as opposed to the use of semantics) found in knowledge bases (KBs) to extract the expansion features. We call our method Structural Query Expansion (SQE). The structural analysis of KBs takes us to propose a set of structural motifs that connect their strongly related entries, which can be used to extract expansion features. In this paper we use Wikipedia as our KB, which is probably one of the largest sources of information. SQE is capable of achieving more than 150% improvement over non expanded queries and is able to identify the expansion features in less than 0.2 seconds in the worst case scenario. Most significantly, we believe that we are contributing to open new research directions in query expansion, proposing a method that is orthogonal to many current systems. For example, SQE improves pseudo-relevance feedback techniques up to 13%

Joan Guisado-Gámez, Arnau Prat-Pérez

Knowledge bases are very good sources for knowledge extraction, the ability to create knowledge from structured and unstructured sources and use it to improve automatic processes as query expansion. However, extracting knowledge from unstructured sources is still an open challenge. In this respect, understanding the structure of knowledge bases can provide significant benefits for the effectiveness of such purpose. In particular, Wikipedia has become a very popular knowledge base in the last years because it is a general encyclopedia that has a large amount of information and thus, covers a large amount of different topics. In this piece of work, we analyze how articles and categories of Wikipedia relate to each other and how these relationships can support a query expansion technique. In particular, we show that the structures in the form of dense cycles with a minimum amount of categories tend to identify the most relevant information.