OpenRaiser/Intern-Atlas huggingface dataset:
Sparse Attack Construction and State Estimation in the Smart Grid: Centralized and Distributed Models
Venue: arXiv cs.IT 2015
Year: 2015

New methods that exploit sparse structures arising in smart grid networks are proposed for the state estimation problem when data injection attacks are present. First, construction strategies for unobservable sparse data injection attacks on power grids are proposed for an attacker with access to all network information and nodes. Specifically, novel formulations for the optimization problem that provide a flexible design of the trade-off between performance and false alarm are proposed. In addition, the centralized case is extended to a distributed framework for both the estimation and attack problems. Different distributed scenarios are proposed depending on assumptions that lead to the spreading of the resources, network nodes and players. Consequently, for each of the presented frameworks a corresponding optimization problem is introduced jointly with an algorithm to solve it. The validity of the presented procedures in real settings is studied through extensive simulations in the IEEE test systems.
A Conceptual Framework for Web Development Projects Based on Project Management and Agile Development Principles
Venue: arXiv cs.SE 2015
Year: 2015

Companies implement different frameworks and best practices with the objective to improve the project management success rate and improve the business adaptability to the changing business environment. Project management framework (PRINCE2) and agile development framework (Scrum) proved in many cases that they can meet these objectives. However, both frameworks are based on different principles and the use of both frameworks together should be carefully considered. A large amount of money and effort has been invested by companies into establishing their project management environment and processes that follow the classical phased approach where requirements are defined upfront and fixed. But companies want to react more quickly to new global challenges and to the changing business environment. These business requirements then result in the failure of many running projects. Therefore there is a need to enhance the current project management environment so that it is more agile and adoptive to changes. The objective of this paper is to create a conceptual framework that aggregates principles and processes from both frameworks (PRINCE2 and Scrum) with emphasis on their use in web development projects. This paper will discuss the advantages and disadvantages of using the two abovementioned frameworks. Different groups of readers can benefit from the results of this paper. It will help corporate management to decide how a company should set up its own specific framework for managing agile product development projects. Project managers will have a better understanding of agile development principles and how it fits in the classic project management framework. Last but not least, it will help product developers to work in more agile ways and survive in the controlled and complex project environment.
Improving Routing Efficiency through Intermediate Target Based Geographic Routing
Venue: arXiv cs.NI 2015
Year: 2015

The greedy strategy of geographical routing may cause the local minimum problem when there is a hole in the routing area. It depends on other strategies such as perimeter routing to find a detour path, which can be long and result in inefficiency of the routing protocol. In this paper, we propose a new approach called Intermediate Target based Geographic Routing (ITGR) to solve the long detour path problem. The basic idea is to use previous experience to determine the destination areas that are shaded by the holes. The novelty of the approach is that a single forwarding path can be used to determine a shaded area that may cover many destination nodes. We design an efficient method for the source to find out whether a destination node belongs to a shaded area. The source then selects an intermediate node as the tentative target and greedily forwards packets to it, which in turn forwards the packet to the final destination by greedy routing. ITGR can combine multiple shaded areas to improve the efficiency of representation and routing. We perform simulations and demonstrate that ITGR significantly reduces the routing path length, compared with existing geographic routing protocols.
Evolution of Directed Triangle Motifs in the Google+ OSN
Venue: arXiv cs.SI 2015
Year: 2015

Motifs are a fundamental building block and distinguishing feature of networks. While characteristic motif distribution have been found in many networks, very little is known today about the evolution of network motifs. This paper studies the most important motifs in social networks, triangles, and how directed triangle motifs change over time. Our chosen subject is one of the largest Online Social Networks, Google+. Google+ has two distinguishing features that make it particularly interesting: (1) it is a directed network, which yields a rich set of triangle motifs, and (2) it is a young and fast evolving network, whose role in the OSN space is still not fully understood. For the purpose of this study, we crawled the network over a time period of six weeks, collecting several snapshots. We find that some triangle types display significant dynamics, e.g., for some specific initial types, up to 20% of the instances evolve to other types. Due to the fast growth of the OSN in the observed time period, many new triangles emerge. We also observe that many triangles evolve into less-connected motifs (with less edges), suggesting that growth also comes with pruning. We complement the topological study by also considering publicly available user profile data (mostly geographic locations). The corresponding results shed some light on the semantics of the triangle motifs. Indeed, we find that users in more symmetric triangle motifs live closer together, indicating more personal relationships. In contrast, asymmetric links in motifs often point to faraway users with a high in-degree (celebrities).
On Counterexample Guided Quantifier Instantiation for Synthesis in CVC4
Venue: arXiv cs.LO 2015
Year: 2015

We introduce the first program synthesis engine implemented inside an SMT solver. We present an approach that extracts solution functions from unsatisfiability proofs of the negated form of synthesis conjectures. We also discuss novel counterexample-guided techniques for quantifier instantiation that we use to make finding such proofs practically feasible. A particularly important class of specifications are single-invocation properties, for which we present a dedicated algorithm. To support syntax restrictions on generated solutions, our approach can transform a solution found without restrictions into the desired syntactic form. As an alternative, we show how to use evaluation function axioms to embed syntactic restrictions into constraints over algebraic datatypes, and then use an algebraic datatype decision procedure to drive synthesis. Our experimental evaluation on syntax-guided synthesis benchmarks shows that our implementation in the CVC4 SMT solver is competitive with state-of-the-art tools for synthesis.
Classification and its applications for drug-target interaction identification
Venue: arXiv cs.LG 2015
Year: 2015

Classification is one of the most popular and widely used supervised learning tasks, which categorizes objects into predefined classes based on known knowledge. Classification has been an important research topic in machine learning and data mining. Different classification methods have been proposed and applied to deal with various real-world problems. Unlike unsupervised learning such as clustering, a classifier is typically trained with labeled data before being used to make prediction, and usually achieves higher accuracy than unsupervised one. In this paper, we first define classification and then review several representative methods. After that, we study in details the application of classification to a critical problem in drug discovery, i.e., drug-target prediction, due to the challenges in predicting possible interactions between drugs and targets.
On the Minimum Cost Range Assignment Problem
Venue: arXiv cs.CG 2015
Year: 2015

We study the problem of assigning transmission ranges to radio stations placed arbitrarily in a $d$-dimensional ($d$-D) Euclidean space in order to achieve a strongly connected communication network with minimum total power consumption. The power required for transmitting in range $r$ is proportional to $r^α$, where $α$ is typically between $1$ and $6$, depending on various environmental factors. While this problem can be solved optimally in $1$D, in higher dimensions it is known to be $NP$-hard for any $α\geq 1$. For the $1$D version of the problem, i.e., radio stations located on a line and $α\geq 1$, we propose an optimal $O(n^2)$-time algorithm. This improves the running time of the best known algorithm by a factor of $n$. Moreover, we show a polynomial-time algorithm for finding the minimum cost range assignment in $1$D whose induced communication graph is a $t$-spanner, for any $t \geq 1$. In higher dimensions, finding the optimal range assignment is $NP$-hard; however, it can be approximated within a constant factor. The best known approximation ratio is for the case $α=1$, where the approximation ratio is $1.5$. We show a new approximation algorithm with improved approximation ratio of $1.5-ε$, where $ε>0$ is a small constant.
Synthesis of Attributed Feature Models From Product Descriptions: Foundations
Venue: arXiv cs.SE 2015
Year: 2015

Feature modeling is a widely used formalism to characterize a set of products (also called configurations). As a manual elaboration is a long and arduous task, numerous techniques have been proposed to reverse engineer feature models from various kinds of artefacts. But none of them synthesize feature attributes (or constraints over attributes) despite the practical relevance of attributes for documenting the different values across a range of products. In this report, we develop an algorithm for synthesizing attributed feature models given a set of product descriptions. We present sound, complete, and parametrizable techniques for computing all possible hierarchies, feature groups, placements of feature attributes, domain values, and constraints. We perform a complexity analysis w.r.t. number of features, attributes, configurations, and domain size. We also evaluate the scalability of our synthesis procedure using randomized configuration matrices. This report is a first step that aims to describe the foundations for synthesizing attributed feature models.
On Crowdsourced Interactive Live Streaming: A Twitch.TV-Based Measurement Study
Venue: arXiv cs.MM 2015
Year: 2015

Empowered by today's rich tools for media generation and collaborative production, the multimedia service paradigm is shifting from the conventional single source, to multi-source, to many sources, and now toward {\em crowdsource}. Such crowdsourced live streaming platforms as Twitch.tv allow general users to broadcast their content to massive viewers, thereby greatly expanding the content and user bases. The resources available for these non-professional broadcasters however are limited and unstable, which potentially impair the streaming quality and viewers' experience. The diverse live interactions among the broadcasters and viewers can further aggravate the problem. In this paper, we present an initial investigation on the modern crowdsourced live streaming systems. Taking Twitch as a representative, we outline their inside architecture using both crawled data and captured traffic of local broadcasters/viewers. Closely examining the access data collected in a two-month period, we reveal that the view patterns are determined by both events and broadcasters' sources. Our measurements explore the unique source- and event-driven views, showing that the current delay strategy on the viewer's side substantially impacts the viewers' interactive experience, and there is significant disparity between the long broadcast latency and the short live messaging latency. On the broadcaster's side, the dynamic uploading capacity is a critical challenge, which noticeably affects the smoothness of live streaming for viewers.
Exact tensor completion using t-SVD
Venue: arXiv cs.LG 2015
Year: 2015

In this paper we focus on the problem of completion of multidimensional arrays (also referred to as tensors) from limited sampling. Our approach is based on a recently proposed tensor-Singular Value Decomposition (t-SVD) [1]. Using this factorization one can derive notion of tensor rank, referred to as the tensor tubal rank, which has optimality properties similar to that of matrix rank derived from SVD. As shown in [2] some multidimensional data, such as panning video sequences exhibit low tensor tubal rank and we look at the problem of completing such data under random sampling of the data cube. We show that by solving a convex optimization problem, which minimizes the tensor nuclear norm obtained as the convex relaxation of tensor tubal rank, one can guarantee recovery with overwhelming probability as long as samples in proportion to the degrees of freedom in t-SVD are observed. In this sense our results are order-wise optimal. The conditions under which this result holds are very similar to the incoherency conditions for the matrix completion, albeit we define incoherency under the algebraic set-up of t-SVD. We show the performance of the algorithm on some real data sets and compare it with other existing approaches based on tensor flattening and Tucker decomposition.
Undecidability of Multiplicative Subexponential Logic
Venue: arXiv cs.LO 2015
Year: 2015

Subexponential logic is a variant of linear logic with a family of exponential connectives--called subexponentials--that are indexed and arranged in a pre-order. Each subexponential has or lacks associated structural properties of weakening and contraction. We show that classical propositional multiplicative linear logic extended with one unrestricted and two incomparable linear subexponentials can encode the halting problem for two register Minsky machines, and is hence undecidable.
Ludics without Designs I: Triads
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we introduce the concept of triad. Using this notion, we study, revisit, discover and rediscover some basic properties of ludics from a very general point of view.
Technical solutions to resources allocation for distributed virtual machine systems
Venue: arXiv cs.DC 2015
Year: 2015

Virtual machine is built on group of real servers which are scattered globally and connect together through the telecommunications systems, it has an increasingly important role in the operation, providing the ability to exploit virtual resources. The latest technique helps to use computing resources more effectively and has many benefits, such as cost reduction of power, cooling and, hence, contributes to the Green Computing. To ensure the supply of these resources to demand processes correctly and promptly, avoiding any duplication or conflict, especially remote resources, it is necessary to study and propose a reliable solution appropriate to be the foundation for internal control systems in the cloud. In the scope of this paper, we find a way to produce efficient distributed resources which emphasizes solutions preventing deadlock and proposing methods to avoid resource shortage issue. With this approach, the outcome result is the checklist of re-sources state which has the possibility of deadlock and lack of resources, by sending messages to the servers, the server would know the situation and have corresponding reaction.
An IDS scheme against Black hole Attack to Secure AOMDV Routing in MANET
Venue: arXiv cs.NI 2015
Year: 2015

In Mobile Ad hoc Network (MANET) all the nodes are freely moves in the absence of without ant centralized coordination system. Due to that the attackers or malicious nodes are easily affected that kind of network and responsible for the routing misbehavior. The routing is network is mandatory to deliver data in between source and destination. In this research we work on security field in MANET and proposed a novel security scheme against routing misbehavior through Black hole attack. The Ad hoc On demand Multipath Routing (AOMDV) protocol is consider for routing and also to improves the routing quality as compare to single path routing protocol. The attacker is affected all the possible paths that is selected by sender for sending data in network. The malicious nodes are forward optimistic reply at the time of routing by that their identification is also a complex procedure. The proposed Intrusion Detection System (IDS) scheme is identified the attacker information through hop count mechanism. The routing information of actual data is reached to which intermediate node and the next hop information is exist at that node is confirm by IDS scheme. The black hole attacker node Identification (ID) is forward in network by that in future attacker is not participating in routing procedure. The proposed security scheme detects and provides the deterrence against routing misbehavior through malicious attack. Here we compare the routing performance of AOMDV, Attack and IDS scheme. The performance of normal multipath routing and proposed IDS scheme is almost equal. The attacker has degrades the whole routing performance but observed that in presence of attacker, routing misbehavior is completely block by the proposed IDS scheme and recovers 95 % of data as compare to normal routing. Keywords- -AOMDV, MANET, IDS, Black hole attack, Routing misbehavior.
Reconfiguration on sparse graphs
Venue: arXiv cs.CC 2015
Year: 2015

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions S and T of size k, whether it is possible to transform S into T by a sequence of vertex additions and deletions such that each intermediate set is also a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set. We denote the former by ISR and the latter by DSR. Both ISR and DSR are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that ISR is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere-dense. As a corollary, we answer positively an open question concerning the parameterized complexity of the problem on graphs of bounded treewidth. Moreover, our techniques generalize recent results showing that ISR is fixed-parameter tractable on planar graphs and graphs of bounded degree. For DSR, we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques, a class of graphs which includes graphs of bounded degeneracy and nowhere-dense graphs.
The Complexity of Synthesis from Probabilistic Components
Venue: arXiv cs.LO 2015
Year: 2015

The synthesis problem asks for the automatic construction of a system from its specification. In the traditional setting, the system is "constructed from scratch" rather than composed from reusable components. However, this is rare in practice, and almost every non-trivial software system relies heavily on the use of libraries of reusable components. Recently, Lustig and Vardi introduced dataflow and controlflow synthesis from libraries of reusable components. They proved that dataflow synthesis is undecidable, while controlflow synthesis is decidable. The problem of controlflow synthesis from libraries of probabilistic components was considered by Nain, Lustig and Vardi, and was shown to be decidable for qualitative analysis (that asks that the specification be satisfied with probability 1). Our main contributions for controlflow synthesis from probabilistic components are to establish better complexity bounds for the qualitative analysis problem, and to show that the more general quantitative problem is undecidable. For the qualitative analysis, we show that the problem (i) is EXPTIME-complete when the specification is given as a deterministic parity word automaton, improving the previously known 2EXPTIME upper bound; and (ii) belongs to UP $\cap$ coUP and is parity-games hard, when the specification is given directly as a parity condition on the components, improving the previously known EXPTIME upper bound.
Network-based statistical comparison of citation topology of bibliographic databases
Venue: arXiv cs.DL 2015
Year: 2015

Modern bibliographic databases provide the basis for scientific research and its evaluation. While their content and structure differ substantially, there exist only informal notions on their reliability. Here we compare the topological consistency of citation networks extracted from six popular bibliographic databases including Web of Science, CiteSeer and arXiv.org. The networks are assessed through a rich set of local and global graph statistics. We first reveal statistically significant inconsistencies between some of the databases with respect to individual statistics. For example, the introduced field bow-tie decomposition of DBLP Computer Science Bibliography substantially differs from the rest due to the coverage of the database, while the citation information within arXiv.org is the most exhaustive. Finally, we compare the databases over multiple graph statistics using the critical difference diagram. The citation topology of DBLP Computer Science Bibliography is the least consistent with the rest, while, not surprisingly, Web of Science is significantly more reliable from the perspective of consistency. This work can serve either as a reference for scholars in bibliometrics and scientometrics or a scientific evaluation guideline for governments and research agencies.
Node mixing and group structure of complex software networks
Venue: arXiv cs.SI 2015
Year: 2015

Large software projects are among most sophisticated human-made systems consisting of a network of interdependent parts. Past studies of software systems from the perspective of complex networks have already led to notable discoveries with different applications. Nevertheless, our comprehension of the structure of software networks remains to be only partial. We here investigate correlations or mixing between linked nodes and show that software networks reveal dichotomous node degree mixing similar to that recently observed in biological networks. We further show that software networks also reveal characteristic clustering profiles and mixing. Hence, node mixing in software networks significantly differs from that in, e.g., the Internet or social networks. We explain the observed mixing through the presence of groups of nodes with common linking pattern. More precisely, besides densely linked groups known as communities, software networks also consist of disconnected groups denoted modules, core/periphery structures and other. Moreover, groups coincide with the intrinsic properties of the underlying software projects, which promotes practical applications in software engineering.