OpenRaiser/Intern-Atlas huggingface dataset:
From Social Data Mining to Forecasting Socio-Economic Crisis
Venue: arXiv cs.CY 2011
Year: 2011

Socio-economic data mining has a great potential in terms of gaining a better understanding of problems that our economy and society are facing, such as financial instability, shortages of resources, or conflicts. Without large-scale data mining, progress in these areas seems hard or impossible. Therefore, a suitable, distributed data mining infrastructure and research centers should be built in Europe. It also appears appropriate to build a network of Crisis Observatories. They can be imagined as laboratories devoted to the gathering and processing of enormous volumes of data on both natural systems such as the Earth and its ecosystem, as well as on human techno-socio-economic systems, so as to gain early warnings of impending events. Reality mining provides the chance to adapt more quickly and more accurately to changing situations. Further opportunities arise by individually customized services, which however should be provided in a privacy-respecting way. This requires the development of novel ICT (such as a self- organizing Web), but most likely new legal regulations and suitable institutions as well. As long as such regulations are lacking on a world-wide scale, it is in the public interest that scientists explore what can be done with the huge data available. Big data do have the potential to change or even threaten democratic societies. The same applies to sudden and large-scale failures of ICT systems. Therefore, dealing with data must be done with a large degree of responsibility and care. Self-interests of individuals, companies or institutions have limits, where the public interest is affected, and public interest is not a sufficient justification to violate human rights of individuals. Privacy is a high good, as confidentiality is, and damaging it would have serious side effects for society.
Quickest Path Queries on Transportation Network
Venue: arXiv cs.CG 2011
Year: 2011

This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveller may enter and exit the network at any point on the roads. Along any road the traveller moves with a fixed speed depending on the road, and outside the network the traveller moves at unit speed in any direction. We give an exact algorithm for the basic version of the problem: given a transportation network of total complexity n in the Euclidean plane, a source point s and a destination point t, and the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n^2 log n) into a data structure of size O(n^2) such that (1 + ε)-approximate cheapest path cost queries between any two points in the plane can be answered in time O(1ε^4 log n).
Closed-set-based Discovery of Bases of Association Rules
Venue: arXiv cs.LG 2011
Year: 2011

The output of an association rule miner is often huge in practice. This is why several concise lossless representations have been proposed, such as the "essential" or "representative" rules. We revisit the algorithm given by Kryszkiewicz (Int. Symp. Intelligent Data Analysis 2001, Springer-Verlag LNCS 2189, 350-359) for mining representative rules. We show that its output is sometimes incomplete, due to an oversight in its mathematical validation. We propose alternative complete generators and we extend the approach to an existing closure-aware basis similar to, and often smaller than, the representative rules, namely the basis B*.
Initial Semantics for higher-order typed syntax in Coq
Venue: arXiv cs.LO 2011
Year: 2011

Initial Semantics aims at characterizing the syntax associated to a signature as the initial object of some category. We present an initial semantics result for typed higher-order syntax together with its formalization in the Coq proof assistant. The main theorem was first proved on paper in the second author's PhD thesis in 2010, and verified formally shortly afterwards. To a simply-typed binding signature S over a fixed set T of object types we associate a category called the category of representations of S. We show that this category has an initial object Sigma(S). From its construction it will be clear that the object Sigma(S) merits the name abstract syntax associated to S. Our theorem is implemented and proved correct in the proof assistant Coq through heavy use of dependent types. The approach through monads gives rise to an implementation of syntax where both terms and variables are intrinsically typed, i.e. where the object types are reflected in the meta-level types. This article is to be seen as a research article rather than about the formalization of a classical mathematical result. The nature of our theorem - involving lengthy, technical proofs and complicated algebraic structures - makes it particularly interesting for formal verification. Our goal is to promote the use of computer theorem provers as research tools, and, accordingly, a new way of publishing mathematical results: a parallel description of a theorem and its formalization should allow the verification of correct transcription of definitions and statements into the proof assistant, and straightforward but technical proofs should be well-hidden in a digital library. We argue that Coq's rich type theory, combined with its various features such as implicit arguments, allows a particularly readable formalization and is hence well-suited for communicating mathematics.
Treemaps with Bounded Aspect Ratio
Venue: arXiv cs.CG 2011
Year: 2011

Treemaps are a popular technique to visualize hierarchical data. The input is a weighted tree $\tree$ where the weight of each node is the sum of the weights of its children. A treemap for $\tree$ is a hierarchical partition of a rectangle into simply connected regions, usually rectangles. Each region represents a node of $\tree$ and its area is proportional to the weight of the corresponding node. An important quality criterion for treemaps is the aspect ratio of its regions. One cannot bound the aspect ratio if the regions are restricted to be rectangles. In contrast, \emph{polygonal partitions}, that use convex polygons, have bounded aspect ratio. We are the first to obtain convex partitions with optimal aspect ratio $O(\depth(\tree))$. However, $\depth(\tree)$ still depends on the input tree. Hence we introduce a new type of treemaps, namely \emph{orthoconvex treemaps}, where regions representing leaves are rectangles, L-, and S-shapes, and regions representing internal nodes are orthoconvex polygons. We prove that any input tree, irrespective of the weights of the nodes and the depth of the tree, admits an orthoconvex treemap of constant aspect ratio. We also obtain several specialized results for single-level treemaps, that is, treemaps where the input tree has depth~1.
Syntax and Semantics of Babel-17
Venue: arXiv cs.PL 2011
Year: 2011

We present Babel-17, the first programming language for purely functional structured programming (PFSP). Earlier work illustrated PFSP in the framework of a toy research language. Babel-17 takes this earlier work to a new level by showing how PFSP can be combined with pattern matching, object oriented programming, and features like concurrency, lazy evaluation, memoization and support for lenses.
Precedence Automata and Languages
Venue: arXiv cs.FL 2011
Year: 2011

Operator precedence grammars define a classical Boolean and deterministic context-free family (called Floyd languages or FLs). FLs have been shown to strictly include the well-known visibly pushdown languages, and enjoy the same nice closure properties. We introduce here Floyd automata, an equivalent operational formalism for defining FLs. This also permits to extend the class to deal with infinite strings to perform for instance model checking.
Long Tail Behavior of Queue Lengths in Broadband Networks: Tsallis Entropy Framework
Venue: arXiv cs.NI 2011
Year: 2011

A maximum entropy framework based on Tsallis entropy is proposed to depict long tail behavior of queue lengths in broadband networks. Queue length expression as measured in terms of number of packets involves Hurwitz-zeta function. When the entropy parameter q in Tsallis entropy is less than unity, the distribution of packets yields power law behavior. In the limit q tending to unity, Tsallis entropy expression reduces to one due to Shannon and well-known results of M/M/1 queuing system are recovered. Relationship between Tsallis entropy parameter q and Hurst parameter H (measure of self-similarity) is postulated. A numerical procedure based on Newton-Raphson method is outlined to compute Lagrange's parameter b. Various relationships between traffic intensity r and Lagrange's parameter b are examined using data generated from mean number of packets from storage model due to Norros. It is found that best fit corresponds to r being a linear combination of decaying exponential and power exponent in b for different values of entropy parameter q. Explicit expression for the probability that queue size exceeds a certain value is derived and it is established that it asymptotically follows power law for q less than one. The system utilization shows an interesting behavior when the parameter r is varied. It attains lower values than that of M/M/1 system for smaller values of r whereas situation reverses for higher values of r.
A note about a partial no-go theorem for quantum PCP
Venue: arXiv cs.CC 2011
Year: 2011

This is not a disproof of the quantum PCP conjecture! In this note we use perturbation on the commuting Hamiltonian problem on a graph, based on results by Bravyi and Vyalyi, to provide a partial no-go theorem for quantum PCP. Specifically, we derive an upper bound on how large the promise gap can be for the quantum PCP still to hold, as a function of the non-commuteness of the system. As the system becomes more and more commuting, the maximal promise gap shrinks. We view these results as possibly a preliminary step towards disproving the quantum PCP conjecture. A different way to view these results is actually as indications that a critical point exists, beyond which quantum PCP indeed holds; in any case, we hope that these results will lead to progress on this important open problem.
The model checking problem for intuitionistic propositional logic with one variable is AC1-complete
Venue: arXiv cs.CC 2011
Year: 2011

We show that the model checking problem for intuitionistic propositional logic with one variable is complete for logspace-uniform AC1. As basic tool we use the connection between intuitionistic logic and Heyting algebra, and investigate its complexity theoretical aspects. For superintuitionistic logics with one variable, we obtain NC1-completeness for the model checking problem.
Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time
Venue: arXiv cs.DM 2011
Year: 2011

A graph is a $k$-leaf power of a tree $T$ if its vertices are leaves of $T$ and two vertices are adjacent in $T$ if and only if their distance in $T$ is at most $k$. Then $T$ is a $k$-leaf root of $G$. This notion was introduced by Nishimura, Ragde, and Thilikos [2002] motivated by the search for underlying phylogenetic trees. We study here an extension of the $k$-leaf power graph recognition problem. This extension is motivated by a new biological question for the evaluation of the latteral gene transfer on a population of viruses. We allow the host graph to slightly differs from a tree and allow some cycles. In fact we study phylogenetic galled networks in which cycles are pairwise vertex disjoint. We show some structural results and propose polynomial algorithms for the cases $k=3$ and $k=4$. As a consequence, squares of galled networks can also be recognized in polynomial time.
Near approximation of maximum weight matching through efficient weight reduction
Venue: arXiv cs.DS 2011
Year: 2011

Let G be an edge-weighted hypergraph on n vertices, m edges of size \le s, where the edges have real weights in an interval [1,W]. We show that if we can approximate a maximum weight matching in G within factor alpha in time T(n,m,W) then we can find a matching of weight at least (alpha-epsilon) times the maximum weight of a matching in G in time (epsilon^{-1})^{O(1)}max_{1\le q \le O(epsilon \frac {log {\frac n {epsilon}}} {log epsilon^{-1}})} max_{m_1+...m_q=m} sum_1^qT(min{n,sm_j},m_{j},(epsilon^{-1})^{O(epsilon^{-1})}). In particular, if we combine our result with the recent (1-ε)-approximation algorithm for maximum weight matching in graphs due to Duan and Pettie whose time complexity has a poly-logarithmic dependence on W then we obtain a (1-ε)-approximation algorithm for maximum weight matching in graphs running in time (epsilon^{-1})^{O(1)}(m+n).
Social Norms for Online Communities
Venue: arXiv cs.SI 2011
Year: 2011

Sustaining cooperation among self-interested agents is critical for the proliferation of emerging online social communities, such as online communities formed through social networking services. Providing incentives for cooperation in social communities is particularly challenging because of their unique features: a large population of anonymous agents interacting infrequently, having asymmetric interests, and dynamically joining and leaving the community; operation errors; and low-cost reputation whitewashing. In this paper, taking these features into consideration, we propose a framework for the design and analysis of a class of incentive schemes based on a social norm, which consists of a reputation scheme and a social strategy. We first define the concept of a sustainable social norm under which every agent has an incentive to follow the social strategy given the reputation scheme. We then formulate the problem of designing an optimal social norm, which selects a social norm that maximizes overall social welfare among all sustainable social norms. Using the proposed framework, we study the structure of optimal social norms and the impacts of punishment lengths and whitewashing on optimal social norms. Our results show that optimal social norms are capable of sustaining cooperation, with the amount of cooperation varying depending on the community characteristics.
Diffusion of Confidential Information on Networks
Venue: arXiv cs.SI 2011
Year: 2011

This is a natural generalization of the previous work by Dan, "Modeling and Simulation of Diffusion Phenomena on Social Networks," to appear in The proceedings of 2011 Third International Conference on Computer Modeling and Simulation. In this paper, we consider the diffusion phenomena of personal or secret information on the variety of networks, such as complete, random, stochastic and scale-free networks.
The Role of Computer Graphics in Documentary Film Production
Venue: arXiv cs.GR 2011
Year: 2011

We discuss a topic on the role of computer graphics in the production of documentaries, which is often ignored in favor of other topics. Typically, except for some rare occasions, documentary producers and computer scientists or digital artists that do computer graphics are relatively far apart in their domains and rarely intercommunicate to have a joint production; yet it happens, and perhaps more so in the present and the future. We attempt to classify the documentaries on the amount and techniques of computer graphics used for documentaries. We come up with the initial categories such as "plain" (no graphics), "in-between", "all-out" -- nearly 100% of the documentary consisting of computer-generated imagery. Computer graphics can be used to enhance the scenery, fill in the gaps in the missing storyline pieces, or animate between scenes. It can incorporate stereoscopic effects for higher viewer impression as well as interactivity aspects. It can also be used simply in old archived image and film restoration.
Multiplicative Drift Analysis
Venue: arXiv cs.NE 2011
Year: 2011

In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multiplicative version of the classical drift theorem. This allows easier analyses in those settings where the optimization progress is roughly proportional to the current distance to the optimum. To display the strength of this tool, we regard the classical problem how the (1+1) Evolutionary Algorithm optimizes an arbitrary linear pseudo-Boolean function. Here, we first give a relatively simple proof for the fact that any linear function is optimized in expected time $O(n \log n)$, where $n$ is the length of the bit string. Afterwards, we show that in fact any such function is optimized in expected time at most ${(1+o(1)) 1.39 \euler n\ln (n)}$, again using multiplicative drift analysis. We also prove a corresponding lower bound of ${(1-o(1))e n\ln(n)}$ which actually holds for all functions with a unique global optimum. We further demonstrate how our drift theorem immediately gives natural proofs (with better constants) for the best known runtime bounds for the (1+1) Evolutionary Algorithm on combinatorial problems like finding minimum spanning trees, shortest paths, or Euler tours.
O Algoritmo usado no programa de criptografia PASME
Venue: arXiv cs.CR 2011
Year: 2011

This work present the main encryption's algorithm of the PASME tool. This software allows encrypt and hide an information in various types of files. The algorithm uses the fact that factoring large numbers is a difficult issue in terms of computational performing to make the main steps of the encryption.
Refinement Types as Higher Order Dependency Pairs
Venue: arXiv cs.LO 2011
Year: 2011

Refinement types are a well-studied manner of performing in-depth analysis on functional programs. The dependency pair method is a very powerful method used to prove termination of rewrite systems; however its extension to higher order rewrite systems is still the object of active research. We observe that a variant of refinement types allow us to express a form of higher-order dependency pair criterion that only uses information at the type level, and we prove the correctness of this criterion.
Cryptolysis v.0.0.1 - A Framework for Automated Cryptanalysis of Classical Ciphers
Venue: arXiv cs.CR 2011
Year: 2011

Cryptolysis is a framework that includes a collection of automated attacks on the classical ciphers based on the article by Clark Dawson on Optimisation heuristics for the automated cryptanalysis of classical ciphers from the Journal of Combinatorial Mathematics and Combinatorial Computing, 1998.
Statistical Analysis of Link Scheduling on Long Paths
Venue: arXiv cs.NI 2011
Year: 2011

We study how the choice of packet scheduling algorithms influences end-to-end performance on long network paths. Taking a network calculus approach, we consider both deterministic and statistical performance metrics. A key enabling contribution for our analysis is a significantly sharpened method for computing a statistical bound for the service given to a flow by the network as a whole. For a suitably parsimonious traffic model we develop closed-form expressions for end-to-end delays, backlog, and output burstiness. The deterministic versions of our bounds yield optimal bounds on end-to-end backlog and output burstiness for some schedulers, and are highly accurate for end-to-end delay bounds.
Asynchronous Code-Division Random Access Using Convex Optimization
Venue: arXiv cs.IT 2011
Year: 2011

Many applications in cellular systems and sensor networks involve a random subset of a large number of users asynchronously reporting activity to a base station. This paper examines the problem of multiuser detection (MUD) in random access channels for such applications. Traditional orthogonal signaling ignores the random nature of user activity in this problem and limits the total number of users to be on the order of the number of signal space dimensions. Contention-based schemes, on the other hand, suffer from delays caused by colliding transmissions and the hidden node problem. In contrast, this paper presents a novel pairing of an asynchronous non-orthogonal code-division random access scheme with a convex optimization-based MUD algorithm that overcomes the issues associated with orthogonal signaling and contention-based methods. Two key distinguishing features of the proposed MUD algorithm are that it does not require knowledge of the delay or channel state information of every user and it has polynomial-time computational complexity. The main analytical contribution of this paper is the relationship between the performance of the proposed MUD algorithm in the presence of arbitrary or random delays and two simple metrics of the set of user codewords. The study of these metrics is then focused on two specific sets of codewords, random binary codewords and specially constructed algebraic codewords, for asynchronous random access. The ensuing analysis confirms that the proposed scheme together with either of these two codeword sets significantly outperforms the orthogonal signaling-based random access in terms of the total number of users in the system.
Does Aesthetics of Web Page Interface Matters to Mandarin Learning?
Venue: arXiv cs.HC 2011
Year: 2011

Aesthetics of web page refers to how attractive a web page is in which it catches the attention of the user to read through the information. In addition, the visual appearance is important in getting attentions of the users. Moreover, it was found that those screens, which were perceived as aesthetically pleasing, were having a better usability. Usability might be a strong basic in relating to the applicability for learning, and in this study pertaining to Mandarin learning. It was also found that aesthetically pleasing layouts of web page would motivate students in Mandarin learning The Mandarin Learning web pages were manipulated according to the desired aesthetic measurements. GUI aesthetic measuring method was used for this purpose. The Aesthetics-Measurement Application (AMA) accomplished with six aesthetic measures was developed and used. On top of it, questionnaires were distributed to the users to gather information on the students' perceptions on the aesthetic aspects and learning aspects. Respondents for this study were students taking Mandarin course level I at UiTM Terengganu. A significant correlation of the aesthetic aspect was found with its relevance to Mandarin learning. In summary, aesthetics should not be ignored or overlooked in designing effective learning interfaces for educational purposes.
On the Windfall and Price of Friendship: Inoculation Strategies on Social Networks
Venue: arXiv cs.GT 2011
Year: 2011

This article investigates selfish behavior in games where players are embedded in a social context. A framework is presented which allows us to measure the Windfall of Friendship, i.e., how much players benefit (compared to purely selfish environments) if they care about the welfare of their friends in the social network graph. As a case study, a virus inoculation game is examined. We analyze the corresponding Nash equilibria and show that the Windfall of Friendship can never be negative. However, we find that if the valuation of a friend is independent of the total number of friends, the social welfare may not increase monotonically with the extent to which players care for each other; intriguingly, in the corresponding scenario where the relative importance of a friend declines, the Windfall is monotonic again. This article also studies convergence of best-response sequences. It turns out that in social networks, convergence times are typically higher and hence constitute a price of friendship. While such phenomena may be known on an anecdotal level, our framework allows us to quantify these effects analytically. Our formal insights on the worst case equilibria are complemented by simulations shedding light onto the structure of other equilibria.