OpenRaiser/Intern-Atlas huggingface dataset:
A Linear Time Active Learning Algorithm for Link Classification -- Full Version --
Venue: arXiv cs.LG 2013
Year: 2013

We present very efficient active learning algorithms for link classification in signed networks. Our algorithms are motivated by a stochastic model in which edge labels are obtained through perturbations of a initial sign assignment consistent with a two-clustering of the nodes. We provide a theoretical analysis within this model, showing that we can achieve an optimal (to whithin a constant factor) number of mistakes on any graph G = (V,E) such that |E| = Ω(|V|^{3/2}) by querying O(|V|^{3/2}) edge labels. More generally, we show an algorithm that achieves optimality to within a factor of O(k) by querying at most order of |V| + (|V|/k)^{3/2} edge labels. The running time of this algorithm is at most of order |E| + |V|\log|V|.
Ontology-based Recommender System of Economic Articles
Venue: arXiv cs.IR 2013
Year: 2013

Decision makers need economical information to drive their decisions. The Company Actualis SARL is specialized in the production and distribution of a press review about French regional economic actors. This economic review represents for a client a prospecting tool on partners and competitors. To reduce the overload of useless information, the company is moving towards a customized review for each customer. Three issues appear to achieve this goal. First, how to identify the elements in the text in order to extract objects that match with the recommendation's criteria presented? Second, How to define the structure of these objects, relationships and articles in order to provide a source of knowledge usable by the extraction process to produce new knowledge from articles? The latter issue is the feedback on customer experience to identify the quality of distributed information in real-time and to improve the relevance of the recommendations. This paper presents a new type of recommendation based on the semantic description of both articles and user profile.
A Scalable Distributed Architecture for Network- and QoS-aware Service Composition
Venue: arXiv cs.DC 2013
Year: 2013

Service-Oriented Computing (SOC) enables the composition of loosely coupled service agents provided with varying Quality of Service (QoS) levels, effectively forming a multiagent system (MAS). Selecting a (near-)optimal set of services for a composition in terms of QoS is crucial when many functionally equivalent services are available. As the number of distributed services, especially in the cloud, is rising rapidly, the impact of the network on the QoS keeps increasing. Despite this and opposed to most MAS approaches, current service approaches depend on a centralized architecture which cannot adapt to the network. Thus, we propose a scalable distributed architecture composed of a flexible number of distributed control nodes. Our architecture requires no changes to existing services and adapts from a centralized to a completely distributed realization by adding control nodes as needed. Also, we propose an extended QoS aggregation algorithm that allows to accurately estimate network QoS. Finally, we evaluate the benefits and optimality of our architecture in a distributed environment.
Integration of knowledge to support automatic object reconstruction from images and 3D data
Venue: arXiv cs.CG 2013
Year: 2013

Object reconstruction is an important task in many fields of application as it allows to generate digital representations of our physical world used as base for analysis, planning, construction, visualization or other aims. A reconstruction itself normally is based on reliable data (images, 3D point clouds for example) expressing the object in his complete extent. This data then has to be compiled and analyzed in order to extract all necessary geometrical elements, which represent the object and form a digital copy of it. Traditional strategies are largely based on manual interaction and interpretation, because with increasing complexity of objects human understanding is inevitable to achieve acceptable and reliable results. But human interaction is time consuming and expensive, why many researches has already been invested to use algorithmic support, what allows to speed up the process and to reduce manual work load. Presently most of such supporting algorithms are data-driven and concentate on specific features of the objects, being accessible to numerical models. By means of these models, which normally will represent geometrical (flatness, roughness, for example) or physical features (color, texture), the data is classified and analyzed. This is successful for objects with low complexity, but gets to its limits with increasing complexness of objects. Then purely numerical strategies are not able to sufficiently model the reality. Therefore, the intention of our approach is to take human cognitive strategy as an example, and to simulate extraction processes based on available human defined knowledge for the objects of interest. Such processes will introduce a semantic structure for the objects and guide the algorithms used to detect and recognize objects, which will yield a higher effectiveness. Hence, our research proposes an approach using knowledge to guide the algorithms in 3D point cloud and image processing.
Computational Aspects of the Calculus of Structure
Venue: arXiv cs.LO 2013
Year: 2013

Logic is the science of correct inferences and a logical system is a tool to prove assertions in a certain logic in a correct way. There are many logical systems, and many ways of formalizing them, e.g., using natural deduction or sequent calculus. Calculus of structures (CoS) is a new formalism proposed by Alessio Guglielmi in 2004 that generalizes sequent calculus in the sense that inference rules can be applied at any depth inside a formula, rather than only to the main connective. With this feature, proofs in CoS are shorter than in any other formalism supporting analytical proofs. Although it is great to have the freedom and expressiveness of CoS, under the point of view of proof search more freedom means a larger search space. And that should be restricted when looking for complete automation of deductive systems. Some efforts were made to reduce this non-determinism, but they are all basically operational approaches, and no solid theoretical result regarding the computational behaviour of CoS has been achieved so far. The main focus of this thesis is to discuss ways to propose a proof search strategy for CoS suitable to implementation. This strategy should be theoretical instead of purely operational. We introduce the concept of incoherence number of substructures inside structures and we use this concept to achieve our main result: there is an algorithm that, according to our conjecture, corresponds to a proof search strategy to every provable structure in the subsystem of FBV (the multiplicative linear logic MLL plus the rule mix) containing only pairwise distinct atoms. Our algorithm is implemented and we believe our strategy is a good starting point to exploit the computational aspects of CoS in more general systems, like BV itself.
Improved algorithms and analysis for the laminar matroid secretary problem
Venue: arXiv cs.GT 2013
Year: 2013

In a matroid secretary problem, one is presented with a sequence of objects of various weights in a random order, and must choose irrevocably to accept or reject each item. There is a further constraint that the set of items selected must form an independent set of an associated matroid. Constant-competitive algorithms (algorithms whose expected solution weight is within a constant factor of the optimal) are known for many types of matroid secretary problems. We examine the laminar matroid and show an algorithm achieving provably 0.053 competitive ratio.
Blind Adaptive Algorithms for Decision Feedback DS-CDMA Receivers in Multipath Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this work we examine blind adaptive and iterative decision feedback (DF) receivers for direct sequence code division multiple access (DS-CDMA) systems in frequency selective channels. Code-constrained minimum variance (CMV) and constant modulus (CCM) design criteria for DF receivers based on constrained optimization techniques are investigated for scenarios subject to multipath. Computationally efficient blind adaptive stochastic gradient (SG) and recursive least squares (RLS) algorithms are developed for estimating the parameters of DF detectors along with successive, parallel and iterative DF structures. A novel successive parallel arbitrated DF scheme is presented and combined with iterative techniques for use with cascaded DF stages in order to mitigate the deleterious effects of error propagation. Simulation results for an uplink scenario assess the algorithms, the blind adaptive DF detectors against linear receivers and evaluate the effects of error propagation of the new cancellations techniques against previously reported approaches.
Performance Analysis of Heterogeneous Feedback Design in an OFDMA Downlink with Partial and Imperfect Feedback
Venue: arXiv cs.IT 2013
Year: 2013

Current OFDMA systems group resource blocks into subband to form the basic feedback unit. Homogeneous feedback design with a common subband size is not aware of the heterogeneous channel statistics among users. Under a general correlated channel model, we demonstrate the gain of matching the subband size to the underlying channel statistics motivating heterogeneous feedback design with different subband sizes and feedback resources across clusters of users. Employing the best-M partial feedback strategy, users with smaller subband size would convey more partial feedback to match the frequency selectivity. In order to develop an analytical framework to investigate the impact of partial feedback and potential imperfections, we leverage the multi-cluster subband fading model. The perfect feedback scenario is thoroughly analyzed, and the closed form expression for the average sum rate is derived for the heterogeneous partial feedback system. We proceed to examine the effect of imperfections due to channel estimation error and feedback delay, which leads to additional consideration of system outage. Two transmission strategies: the fix rate and the variable rate, are considered for the outage analysis. We also investigate how to adapt to the imperfections in order to maximize the average goodput under heterogeneous partial feedback.
Complexity of Creative Telescoping for Bivariate Rational Functions
Venue: arXiv cs.SC 2013
Year: 2013

The long-term goal initiated in this work is to obtain fast algorithms and implementations for definite integration in Almkvist and Zeilberger's framework of (differential) creative telescoping. Our complexity-driven approach is to obtain tight degree bounds on the various expressions involved in the method. To make the problem more tractable, we restrict to bivariate rational functions. By considering this constrained class of inputs, we are able to blend the general method of creative telescoping with the well-known Hermite reduction. We then use our new method to compute diagonals of rational power series arising from combinatorics.
The Tree Width of Separation Logic with Recursive Definitions
Venue: arXiv cs.LO 2013
Year: 2013

Separation Logic is a widely used formalism for describing dynamically allocated linked data structures, such as lists, trees, etc. The decidability status of various fragments of the logic constitutes a long standing open problem. Current results report on techniques to decide satisfiability and validity of entailments for Separation Logic(s) over lists (possibly with data). In this paper we establish a more general decidability result. We prove that any Separation Logic formula using rather general recursively defined predicates is decidable for satisfiability, and moreover, entailments between such formulae are decidable for validity. These predicates are general enough to define (doubly-) linked lists, trees, and structures more general than trees, such as trees whose leaves are chained in a list. The decidability proofs are by reduction to decidability of Monadic Second Order Logic on graphs with bounded tree width.
International collaboration clusters in Africa
Venue: arXiv cs.DL 2013
Year: 2013

Recent discussion about the increase in international research collaboration suggests a comprehensive global network centred around a group of core countries and driven by generic socio-economic factors where the global system influences all national and institutional outcomes. In counterpoint, we demonstrate that the collaboration pattern for countries in Africa is far from universal. Instead, it exhibits layers of internal clusters and external links that are explained not by monotypic global influences but by regional geography and, perhaps even more strongly, by history, culture and language. Analysis of these bottom-up, subjective, human factors is required in order to provide the fuller explanation useful for policy and management purposes.
Models of Social Groups in Blogosphere Based on Information about Comment Addressees and Sentiments
Venue: arXiv cs.SI 2013
Year: 2013

This work concerns the analysis of number, sizes and other characteristics of groups identified in the blogosphere using a set of models identifying social relations. These models differ regarding identification of social relations, influenced by methods of classifying the addressee of the comments (they are either the post author or the author of a comment on which this comment is directly addressing) and by a sentiment calculated for comments considering the statistics of words present and connotation. The state of a selected blog portal was analyzed in sequential, partly overlapping time intervals. Groups in each interval were identified using a version of the CPM algorithm, on the basis of them, stable groups, existing for at least a minimal assumed duration of time, were identified.
Improved Hardness of Approximating Chromatic Number
Venue: arXiv cs.CC 2013
Year: 2013

We prove that for sufficiently large K, it is NP-hard to color K-colorable graphs with less than 2^{K^{1/3}} colors. This improves the previous result of K versus K^{O(log K)} in Khot [14].
Interactive Traceability Querying and Visualization for Coping With Development Complexity
Venue: arXiv cs.SE 2013
Year: 2013

Requirements traceability can in principle support stakeholders coping with rising development complexity. However, studies showed that practitioners rarely use available traceability information after its initial creation. In the position paper for the Dagstuhl seminar 1242, we argued that a more integrated approach allowing interactive traceability queries and context-specific traceability visualizations is needed to let practitioner access and use valuable traceability information. The information retrieved via traceability can be very specific to a current task of a stakeholder, abstracting from everything that is not required to solve the task.
Auditing scholarly journals published in Malaysia and assessing their visibility
Venue: arXiv cs.DL 2013
Year: 2013

The problem with the identification of Malaysian scholarly journals lies in the lack of a current and complete listing of journals published in Malaysia. As a result, librarians are deprived of a tool that can be used for journal selection and identification of gaps in their serials collection. This study describes the audit carried out on scholarly journals, with the objectives (a) to trace and characterized scholarly journal titles published in Malaysia, and (b) to determine their visibility in international and national indexing databases. A total of 464 titles were traced and their yearly trends, publisher and publishing characteristics, bibliometrics and indexation in national, international and subject-based indexes were described.
Publication productivity and citation analysis of the Medical Journal of Malaysia: 2004 - 2008
Venue: arXiv cs.DL 2013
Year: 2013

We analysed 580 articles (original articles only) published in Medical Journal of Malaysia between 2004 and 2008, the resources referenced by the articles and the citations and impact received. Our aim was to examine article and author productivity, the age of references used and impact of the journal. Publication data was obtained from MyAIS database and Google Scholar provided the citation data. From the 580 articles analyzed, contributors mainly come from the hospitals, universities and clinics. Contributions from foreign authors are low. The useful lives of references cited were between 3 to 11 years. ISI derived Impact factor for MJM ranged between 0.378 to 0.616. Journal self-citation is low. Out of the 580 sampled articles, 76.8% have been cited at least once over the 5 years and the ratio of total publications to citations is 1: 2.6.
International Contribution to Nipah Virus Research 1999-2010
Venue: arXiv cs.DL 2013
Year: 2013

This study examines 462 papers on Nipah virus research published from 1999 to 2010, identifying the active authors, institutions and citations received. Data was extracted from SCI-Expanded database, (Web of Science) and analyzed using descriptive figures and tables. The results show the growth of publication is incremental up to 2010 even though the average citations received is decreasing. The ratio of authors to articles is 1330: 426. The active contributing countries are USA (41.0%), Australia (19.3%), Malaysia (16.0%), England (6.5%) and France (5.6%). The productive authors are mainly affiliated to the Centre for Disease Control and Prevention, USA and Commonwealth Scientific and Industrial Research Organization (CSIRO) in Australia and University of Malaya Medical Centre, Malaysia. A total of 10572 citations were received and the ratio of articles to citation is 1: 24.8. Collaboration with the bigger laboratories in USA and Australia is contributive to the sustained growth of published literature and to access diverse expertise.
Open Access repositories and journals for visibility: Implications for Malaysian libraries
Venue: arXiv cs.DL 2013
Year: 2013

This paper describes the growth of Open Access (OA) repositories and journals as reported by monitoring initiatives such as ROAR (Registry of Open Access Repositories), Open DOAR (Open Directory of Open Access Repositories), DOAJ (Directory of Open Access Journals), Directory of Web Ranking of World Repositories by the Cybermetrics Laboratory in Spain and published literature. The performance of Malaysian OA repositories and journals is highlighted. The strength of OA channels in increasing visibility and citations are evidenced by research findings. It is proposed that libraries champion OA initiatives by making university or institutional governance aware; encouraging institutional journal publishers to adopt OA platform; collaborating with research groups to jumpstart OA institutional initiatives and to embed OA awareness into user and researcher education programmes. By actively involved, libraries will be free of permission, licensing and archiving barriers usually imposed in traditional publishing situation.
The Pattern of E-Book Use amongst Undergraduates an Malaysia: A Case of to Know is to Use
Venue: arXiv cs.DL 2013
Year: 2013

This exploratory study focuses on identifying the usage pattern of e-books especially on how, when, where and why undergraduates at the Faculty of Computer Science and Information Technology (FCSIT), University of Malaya (UM), Kuala Lumpur use or do not use the e-books service provided by the University of Malaya library. A total of 206 (82%) useable questionnaires form the basis of analysis. The results indicate even though the students are heavy users of the Internet, rate themselves as skilled in Internet use and have positive attitude towards the e-book service, the level of e-book use is still low (39%). The students become aware of the e-book service mainly while visiting the University of Malaya Library Website, or are referred to it by their lecturers, friends or the librarians. About 70% rate positively on the e-book service. Those who are users of e-books find e-books easy to use and their usages are mainly for writing assignment or project work. Most respondents prefer to use e-versions of textbooks and reference sources. Generally, both users and non-users of e-books prefer to use the printed version of textbooks especially if the text is continuously used. There are significant difference between the frequency of e-book use and gender; between past usage of e-book and preference for electronic textbooks and reference books. The possible factors which may be related to e-book use are categorized into 4 groups and presented in a model, which comprises the ICT competencies of the students, their cognitive makeup, the degree of user access to the e-books and the functional or use factors.
A2ILU: Auto-accelerated ILU Preconditioner for Sparse Linear Systems
Venue: arXiv cs.NA 2013
Year: 2013

The ILU-based preconditioning methods in previous work have their own parameters to improve their performances. Although the parameters may degrade the performance, their determination is left to users. Thus, these previous methods are not reliable in practical computer-aided engineering use. This paper proposes a novel ILU-based preconditioner called the auto-accelerated ILU, or A2ILU. In order to improve the convergence, A2ILU introduces acceleration parameters which modify the ILU factorized preconditioning matrix. A$^2$ILU needs no more operations than the original ILU because the acceleration parameters are optimized automatically by A2ILU itself. Numerical tests reveal the performance of A2ILU is superior to previous ILU-based methods with manually optimized parameters. The numerical tests also demonstrate the ability to apply auto-acceleration to ILU-based methods to improve their performances and robustness of parameter sensitivities.
Complexity Estimates for Two Uncoupling Algorithms
Venue: arXiv cs.SC 2013
Year: 2013

Uncoupling algorithms transform a linear differential system of first order into one or several scalar differential equations. We examine two approaches to uncoupling: the cyclic-vector method (CVM) and the Danilevski-Barkatou-Zürcher algorithm (DBZ). We give tight size bounds on the scalar equations produced by CVM, and design a fast variant of CVM whose complexity is quasi-optimal with respect to the output size. We exhibit a strong structural link between CVM and DBZ enabling to show that, in the generic case, DBZ has polynomial complexity and that it produces a single equation, strongly related to the output of CVM. We prove that algorithm CVM is faster than DBZ by almost two orders of magnitude, and provide experimental results that validate the theoretical complexity analyses.