356 research outputs found
A unifying framework for l0-sampling algorithms
No full textThe problem of building an l 0-sampler is to sample near-uniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an l 0-sampler, based on sampling, recovery and selection. We analyze the implementation of an l 0-sampler within this framework, and show how prior constructions of l 0-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of l 0-samplers. © 2013 Springer Science+Business Media New York
On unifying the space of l0-sampling algorithms
No full textThe problem of building an l0-sampler is to sample nearuniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an l0-sampler, based on sampling, recovery and selection. We analyze the implementation of an l0-sampler within this framework, and show how prior constructions of l0-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of l0-samplers
The (not so) critical nodes of criminal networks
No full textOne of the most basic question in the analysis of social networks is to find nodes that are of particular relevance in the network. The answer that emerged in the recent literature is that the importance, or centrality, of a node x is proportional to the number of nodes that get disconnected from the network when node x is removed. We show that while in social networks such important nodes lie in their cores (i.e., maximal subgraphs in which all nodes have degree higher than a certain value), this is not necessarily the case in criminal networks. This shows that nodes whose removal affects large portions of the criminal network prefer to operate from network peripheries, thus confirming the intuition of Baker and Faulkner [4]. Our results also highlight structural differences between criminal networks and other social networks, suggesting that classical definitions of importance (or centrality) in a network fail to capture the concept of key players in criminal networks
On the Meaningfulness of “Big Data Quality” (Invited Paper)
No full textIn this paper, we discuss the application of concept of data quality to big data by highlighting how much complex is to define it in a general way. Already data quality is a multidimensional concept, difficult to characterize in precise definitions even in the case of well-structured data. Big data add two further dimensions of complexity: (i) being “very” source specific, and for this we adopt the interesting UNECE classification, and (ii) being highly unstructured and schema-less, often without golden standards to refer to or very difficult to access. After providing a tutorial on data quality in traditional contexts, we analyze big data by providing insights into the UNECE classification, and then, for each type of data source, we choose a specific instance of such a type (notably deep Web data, sensor-generated data, and Twitters/short texts) and discuss how quality dimensions can be defined in these cases. The overall aim of the paper is therefore to identify further research directions in the area of big data quality, by providing at the same time an up-to-date state of the art on data quality. © 2015, The Author(s)
Online entity resolution using an oracle
No full textEntity resolution (ER) is the task of identifying all records in adatabase that refer to the same underlying entity. This is an expensivetask, and can take a significant amount of money and time; theend-user may want to take decisions during the process, rather thanwaiting for the task to be completed. We formalize an online versionof the entity resolution task, and use an oracle which correctlylabels matching and non-matching pairs through queries. In thissetting, we design algorithms that seek to maximize progressive recall,and develop a novel analysis framework for prior proposalson entity resolution with an oracle, beyond their worst case guarantees.Finally, we provide both theoretical and experimental analysisof the proposed algorithms
Multikernel Activation Functions: Formulation and a Case Study
No full textThe design of activation functions is a growing research area in the field of neural networks. In particular, instead of using fixed point-wise functions (e.g., the rectified linear unit), several authors have proposed ways of learning these functions directly from the data in a non-parametric fashion. In this paper we focus on the kernel activation function (KAF), a recently proposed framework wherein each function is modeled as a one-dimensional kernel model, whose weights are adapted through standard backpropagation-based optimization. One drawback of KAFs is the need to select a single kernel function and its eventual hyper-parameters. To partially overcome this problem, we motivate an extension of the KAF model, in which multiple kernels are linearly combined at every neuron, inspired by the literature on multiple kernel learning. We provide an application of the resulting multi-KAF on a realistic use case, specifically handwritten Latin OCR, on a large dataset collected in the context of the ‘In Codice Ratio’ project. Results show that multi-KAFs can improve the accuracy of the convolutional networks previously developed for the task, with faster convergence, even with a smaller number of overall parameters
Real-time Analysis of Critical Nodes in Network Cores
No full textThe articulation points and bridges of a connected network are, respectively, the vertices and the edges whose removal disconnects the network. However, not all the articulation points (resp. bridges) are equal: from the graph theoretic perspective, there is no difference whether the removal of a vertex (resp. bridge) disconnects only one vertex from the rest of the network, or it cuts the network in two pieces. But in the monitoring of a huge network, it makes a difference. We present a real-time algorithm, analyzed in the (semi-)streaming model of computation, that is able to identify a core subset of the articulation points (resp. bridges), i.e. the ones whose removal has a big impact on the network: these are the critical nodes (resp. edges) of the network. We complement our work with an experimental evaluation of the algorithm against ten years of samples of the Autonomous System network, that confirms the effectiveness of our approach
A meta-algorithm for finding large k-plexes
No full textWe focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration
Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components
No full textIn this article, we present the first algorithm in the streaming model to characterize completely the biconnectivity properties of undirected networks: articulation points, bridges, and connected and biconnected components. The motivation of our work was the development of a real-time algorithm to monitor the connectivity of the autonomous systems (AS) network, but the solution provided is general enough to be applied to any network. The network structure is represented by a graph, and the algorithm is analyzed in the datastream framework. Here, as in the on-line model, the input graph is revealed one item (i.e., graph edge) after the other, in an on-line fashion; but, if compared to traditional on-line computation, there are stricter requirements for both memory occupation and per item processing time. Our algorithm works by properly updating a forest over the graph nodes. All the graph (bi)connectivity properties are stored in this forest. We prove the correctness of the algorithm, together with its space (O(nlog n), with n being the number of nodes in the graph) and time bounds. We also present the results of a brief experimental evaluation against real-world graphs, including many samples of the AS network, ranging from medium to massive size. These preliminary experimental results confirm the effectiveness of our approach. © 2012 Wiley Periodicals, Inc. NETWORKS, Vol. 2012 Copyright © 2012 Wiley Periodicals, Inc
Data processing: Reflections on ethics
No full textEthics-related aspects are becoming prominent in data management, thus the current processes for searching, querying, or analyzing data should be designed is such a way as to take into account the social problems their outcomes could bring about. In this paper we provide reections on the unavoidable ethical facets entailed by all the steps of the information life-cycle, including source selection, knowledge extraction, data integration and data analysis. Such reections motivated us to organize the First International Workshop on Processing Information Ethically (PIE)
- …
