OpenRaiser/Intern-Atlas huggingface dataset:
VoG: Summarizing and Understanding Large Graphs
Venue: arXiv cs.SI 2014
Year: 2014

How can we succinctly describe a million-node graph with a few simple sentences? How can we measure the "importance" of a set of discovered subgraphs in a large graph? These are exactly the problems we focus on. Our main ideas are to construct a "vocabulary" of subgraph-types that often occur in real graphs (e.g., stars, cliques, chains), and from a set of subgraphs, find the most succinct description of a graph in terms of this vocabulary. We measure success in a well-founded way by means of the Minimum Description Length (MDL) principle: a subgraph is included in the summary if it decreases the total description length of the graph. Our contributions are three-fold: (a) formulation: we provide a principled encoding scheme to choose vocabulary subgraphs; (b) algorithm: we develop \method, an efficient method to minimize the description cost, and (c) applicability: we report experimental results on multi-million-edge real graphs, including Flickr and the Notre Dame web graph.
Space Saving by Dynamic Algebraization
Venue: arXiv cs.DS 2014
Year: 2014

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithm based on tree decompositions in polynomial space. We show how to construct a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof such that the dynamic programming algorithm runs in time $O^*(2^h)$, where $h$ is the maximum number of vertices in the union of bags on the root to leaf paths on a given tree decomposition, which is a parameter closely related to the tree-depth of a graph. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.
Multiparty Sessions based on Proof Nets
Venue: arXiv cs.LO 2014
Year: 2014

We interpret Linear Logic Proof Nets in a term language based on Solos calculus. The system includes a synchronisation mechanism, obtained by a conservative extension of the logic, that enables to define non-deterministic behaviours and multiparty sessions.
Sessions as Propositions
Venue: arXiv cs.PL 2014
Year: 2014

Recently, Wadler presented a continuation-passing translation from a session-typed functional language, GV, to a process calculus based on classical linear logic, CP. However, this translation is one-way: CP is more expressive than GV. We propose an extension of GV, called HGV, and give translations showing that it is as expressive as CP. The new translations shed light both on the original translation from GV to CP, and on the limitations in expressiveness of GV.
Towards Reversible Sessions
Venue: arXiv cs.PL 2014
Year: 2014

In this work, we incorporate reversibility into structured communication-based programming, to allow parties of a session to automatically undo, in a rollback fashion, the effect of previously executed interactions. This permits taking different computation paths along the same session, as well as reverting the whole session and starting a new one. Our aim is to define a theoretical basis for examining the interplay in concurrent systems between reversible computation and session-based interaction. We thus enrich a session-based variant of pi-calculus with memory devices, dedicated to keep track of the computation history of sessions in order to reverse it. We discuss our initial investigation concerning the definition of a session type discipline for the proposed reversible calculus, and its practical advantages for static verification of safe composition in communication-centric distributed software performing reversible computations.
A Novel Scheme to improve spectrum sensing performance
Venue: arXiv cs.NI 2014
Year: 2014

Due to limited availability of spectrum for licensed users only, the need for secondary access by unlicensed users is increasing. Cognitive radio turns out to be helping this situation because all that is needed is a technique that could efficiently detect the empty spaces and provide them to the secondary devices without causing any interference to the primary (licensed) users. Spectrum sensing is the foremost function of the cognitive radio which senses the environment for white spaces. Energy detection is one of the various spectrum sensing techniques that are under research. Earlier it was shown that energy detection works better under AWGN channel as compared to Rayleigh channel, however the conventional spectrum sensing techniques have a high probability of false alarm and also show a better probability of detection for higher values of SNR. There is a need for a new technique that shows a reduced probability of false alarm as well as an increase in the probability of detection for lower values of SNR. In the present work the conventional energy detection technique has been enhanced to get better results.
Boundary Element Analysis with trimmed NURBS and a generalized IGA approach
Venue: arXiv cs.NA 2014
Year: 2014

A novel approach to the simulation with the boundary element method using trimmed NURBS patches is presented. The advantage of this approach is its efficiency and easy implementation. The analysis with trimmed NURBS is achieved by double mapping. The variation of the unknowns on the boundary is specified in a local coordinate system and is completely independent of the description of the geometry. The method is tested on a branched tunnel and the results compared with those obtained from a conventional analysis. The conclusion is that the proposed approach is superior in terms of number of unknowns and effort required.
Methodological Societies
Venue: arXiv cs.SE 2014
Year: 2014

The evolution of self-adaptive systems poses the problems of their coherence and the resume of the systems' functioning taking into account the accomplished work. While they are the base of the self-adaptive systems, these two aspects are not considered in the related works. In this paper, we propose a methodological based approach. In such approach, the adaptive system's evolution is thought at its model level where its execution is made on the system by exploiting a methodological process. For its concretization, we use colored Petri nets to describe the agents' individual tasks. To handle the system's functioning resume, we exploit the property of Petri nets on which the control flow depends on last marking only.
Compressed Sensing Applied to Weather Radar
Venue: arXiv cs.IT 2014
Year: 2014

We propose an innovative meteorological radar, which uses reduced number of spatiotemporal samples without compromising the accuracy of target information. Our approach extends recent research on compressed sensing (CS) for radar remote sensing of hard point scatterers to volumetric targets. The previously published CS-based radar techniques are not applicable for sampling weather since the precipitation echoes lack sparsity in both range-time and Doppler domains. We propose an alternative approach by adopting the latest advances in matrix completion algorithms to demonstrate the sparse sensing of weather echoes. We use Iowa X-band Polarimetric (XPOL) radar data to test and illustrate our algorithms.
Trace checking of Metric Temporal Logic with Aggregating Modalities using MapReduce
Venue: arXiv cs.SE 2014
Year: 2014

Modern complex software systems produce a large amount of execution data, often stored in logs. These logs can be analyzed using trace checking techniques to check whether the system complies with its requirements specifications. Often these specifications express quantitative properties of the system, which include timing constraints as well as higher-level constraints on the occurrences of significant events, expressed using aggregate operators. In this paper we present an algorithm that exploits the MapReduce programming model to check specifications expressed in a metric temporal logic with aggregating modalities, over large execution traces. The algorithm exploits the structure of the formula to parallelize the evaluation, with a significant gain in time. We report on the assessment of the implementation - based on the Hadoop framework - of the proposed algorithm and comment on its scalability.
Emerging Phishing Trends and Effectiveness of the Anti-Phishing Landing Page
Venue: arXiv cs.CY 2014
Year: 2014

Each month, more attacks are launched with the aim of making web users believe that they are communicating with a trusted entity which compels them to share their personal, financial information. Phishing costs Internet users billions of dollars every year. Researchers at Carnegie Mellon University (CMU) created an anti-phishing landing page supported by Anti-Phishing Working Group (APWG) with the aim to train users on how to prevent themselves from phishing attacks. It is used by financial institutions, phish site take down vendors, government organizations, and online merchants. When a potential victim clicks on a phishing link that has been taken down, he / she is redirected to the landing page. In this paper, we present the comparative analysis on two datasets that we obtained from APWG's landing page log files; one, from September 7, 2008 - November 11, 2009, and other from January 1, 2014 - April 30, 2014. We found that the landing page has been successful in training users against phishing. Forty six percent users clicked lesser number of phishing URLs from January 2014 to April 2014 which shows that training from the landing page helped users not to fall for phishing attacks. Our analysis shows that phishers have started to modify their techniques by creating more legitimate looking URLs and buying large number of domains to increase their activity. We observed that phishers are exploiting ICANN accredited registrars to launch their attacks even after strict surveillance. We saw that phishers are trying to exploit free subdomain registration services to carry out attacks. In this paper, we also compared the phishing e-mails used by phishers to lure victims in 2008 and 2014. We found that the phishing e-mails have changed considerably over time. Phishers have adopted new techniques like sending promotional e-mails and emotionally targeting users in clicking phishing URLs.
Analyzing Social and Stylometric Features to Identify Spear phishing Emails
Venue: arXiv cs.CY 2014
Year: 2014

Spear phishing is a complex targeted attack in which, an attacker harvests information about the victim prior to the attack. This information is then used to create sophisticated, genuine-looking attack vectors, drawing the victim to compromise confidential information. What makes spear phishing different, and more powerful than normal phishing, is this contextual information about the victim. Online social media services can be one such source for gathering vital information about an individual. In this paper, we characterize and examine a true positive dataset of spear phishing, spam, and normal phishing emails from Symantec's enterprise email scanning service. We then present a model to detect spear phishing emails sent to employees of 14 international organizations, by using social features extracted from LinkedIn. Our dataset consists of 4,742 targeted attack emails sent to 2,434 victims, and 9,353 non targeted attack emails sent to 5,912 non victims; and publicly available information from their LinkedIn profiles. We applied various machine learning algorithms to this labeled data, and achieved an overall maximum accuracy of 97.76% in identifying spear phishing emails. We used a combination of social features from LinkedIn profiles, and stylometric features extracted from email subjects, bodies, and attachments. However, we achieved a slightly better accuracy of 98.28% without the social features. Our analysis revealed that social features extracted from LinkedIn do not help in identifying spear phishing emails. To the best of our knowledge, this is one of the first attempts to make use of a combination of stylometric features extracted from emails, and social features extracted from an online social network to detect targeted spear phishing emails.
High Performance Network-on-Chips (NoCs) Design: Performance Modeling, Routing Algorithm and Architecture Optimization
Venue: arXiv cs.OH 2014
Year: 2014

With technology scaling down, hundreds and thousands processing elements (PEs) can be integrated on a single chip. Network-on-chip (NoC) has been proposed as an efficient solution to handle this distinctive challenge. In this thesis, we have explored the high performance NoC design for MPSoC and CMP structures from the performance modeling in the offline design phase to the routing algorithm and NoC architecture optimization. More specifically, we first deal with the issue of how to estimate an NoC design fast and accurately in the synthesis inner loop. For this purpose, we propose a machine learning based latency regression model to evaluate the NoC designs with respect to different configurations. Then, for high performance NoC designs, we tackle one of the most important problems, i.e., the routing algorithms design. For avoiding temperature hotspots, a thermal-aware routing algorithm is proposed to achieve an even temperature profile for application-specific Network-on-chips (NoCs). For improving the reliability, a routing algorithm to achieve maximum performance under fault is proposed. Finally, in the architecture level, we propose two new NoC structures using bi-directional links for the performance optimization. In particular, we propose a flit-level speedup scheme to enhance the network-on-chip(NoC) performance utilizing bidirectional channels. We also propose a flexible NoC architecture which takes advantage of a dynamic distributed routing algorithm and improves the NoC communication performance with moderate energy overhead. From the simulation results on both synthetic traffic and real workload traces, significant performance improvement in terms of latency and throughput can be achieved.
Argument Ranking with Categoriser Function
Venue: arXiv cs.AI 2014
Year: 2014

Recently, ranking-based semantics is proposed to rank-order arguments from the most acceptable to the weakest one(s), which provides a graded assessment to arguments. In general, the ranking on arguments is derived from the strength values of the arguments. Categoriser function is a common approach that assigns a strength value to a tree of arguments. When it encounters an argument system with cycles, then the categoriser strength is the solution of the non-linear equations. However, there is no detail about the existence and uniqueness of the solution, and how to find the solution (if exists). In this paper, we will cope with these issues via fixed point technique. In addition, we define the categoriser-based ranking semantics in light of categoriser strength, and investigate some general properties of it. Finally, the semantics is shown to satisfy some of the axioms that a ranking-based semantics should satisfy.
Human-Machine CRFs for Identifying Bottlenecks in Holistic Scene Understanding
Venue: arXiv cs.CV 2014
Year: 2014

Recent trends in image understanding have pushed for holistic scene understanding models that jointly reason about various tasks such as object detection, scene recognition, shape analysis, contextual reasoning, and local appearance based classifiers. In this work, we are interested in understanding the roles of these different tasks in improved scene understanding, in particular semantic segmentation, object detection and scene recognition. Towards this goal, we "plug-in" human subjects for each of the various components in a state-of-the-art conditional random field model. Comparisons among various hybrid human-machine CRFs give us indications of how much "head room" there is to improve scene understanding by focusing research efforts on various individual tasks.
Quantum finite automata: A modern introduction
Venue: arXiv cs.FL 2014
Year: 2014

We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum computation concepts to computer scientists. We also describe a modern QFA model involving superoperators that is able to simulate all known QFA and classical finite automaton variants.
Constructions of Optimal and Almost Optimal Locally Repairable Codes
Venue: arXiv cs.IT 2014
Year: 2014

Constructions of optimal locally repairable codes (LRCs) in the case of $(r+1) \nmid n$ and over small finite fields were stated as open problems for LRCs in [I. Tamo \emph{et al.}, "Optimal locally repairable codes and connections to matroid theory", \emph{2013 IEEE ISIT}]. In this paper, these problems are studied by constructing almost optimal linear LRCs, which are proven to be optimal for certain parameters, including cases for which $(r+1) \nmid n$. More precisely, linear codes for given length, dimension, and all-symbol locality are constructed with almost optimal minimum distance. `Almost optimal' refers to the fact that their minimum distance differs by at most one from the optimal value given by a known bound for LRCs. In addition to these linear LRCs, optimal LRCs which do not require a large field are constructed for certain classes of parameters.
Broker Bots: Analyzing automated activity during High Impact Events on Twitter
Venue: arXiv cs.SI 2014
Year: 2014

Twitter is now an established and a widely popular news medium. Be it normal banter or a discussion on high impact events like Boston marathon blasts, February 2014 US Icestorm, etc., people use Twitter to get updates. Twitter bots have today become very common and acceptable. People are using them to get updates about emergencies like natural disasters, terrorist strikes, etc. Twitter bots provide these users a means to perform certain tasks on Twitter that are both simple and structurally repetitive. During high impact events these Twitter bots tend to provide time critical and comprehensive information. We present how bots participate in discussions and augment them during high impact events. We identify bots in high impact events for 2013: Boston blasts, February 2014 US Icestorm, Washington Navy Yard Shooting, Oklahoma tornado, and Cyclone Phailin. We identify bots among top tweeters by getting all such accounts manually annotated. We then study their activity and present many important insights. We determine the impact bots have on information diffusion during these events and how they tend to aggregate and broker information from various sources to different users. We also analyzed their tweets, list down important differentiating features between bots and non bots (normal or human accounts) during high impact events. We also show how bots are slowly moving away from traditional API based posts towards web automation platforms like IFTTT, dlvr.it, etc. Using standard machine learning, we proposed a methodology to identify bots/non bots in real time during high impact events. This study also looks into how the bot scenario has changed by comparing data from high impact events from 2013 with data from similar type of events from 2011. Lastly, we also go through an in-depth analysis of Twitter bots who were active during 2013 Boston Marathon Blast.
On MITL and alternating timed automata over infinite words
Venue: arXiv cs.LO 2014
Year: 2014

One clock alternating timed automata (OCATA) have been introduced as natural extension of (one clock) timed automata to express the semantics of MTL. In this paper, we consider the application of OCATA to the problems of model-checking and satisfiability for MITL (a syntactic fragment of MTL), interpreted over infinite words. Our approach is based on the interval semantics (recently introduced in [BEG13] in the case of finite words) extended to infinite words. We propose region-based and zone-based algorithms, based on this semantics, for MITL model-checking and satisfiability. We report on the performance of a prototype tool implementing those algorithms.
The Propagation Depth of Local Consistency
Venue: arXiv cs.AI 2014
Year: 2014

We establish optimal bounds on the number of nested propagation steps in $k$-consistency tests. It is known that local consistency algorithms such as arc-, path- and $k$-consistency are not efficiently parallelizable. Their inherent sequential nature is caused by long chains of nested propagation steps, which cannot be executed in parallel. This motivates the question "What is the minimum number of nested propagation steps that have to be performed by $k$-consistency algorithms on (binary) constraint networks with $n$ variables and domain size $d$?" It was known before that 2-consistency requires $Ω(nd)$ and 3-consistency requires $Ω(n^2)$ sequential propagation steps. We answer the question exhaustively for every $k\geq 2$: there are binary constraint networks where any $k$-consistency procedure has to perform $Ω(n^{k-1}d^{k-1})$ nested propagation steps before local inconsistencies were detected. This bound is tight, because the overall number of propagation steps performed by $k$-consistency is at most $n^{k-1}d^{k-1}$.
A New Advanced User Authentication and Confidentiality Security Service
Venue: arXiv cs.CR 2014
Year: 2014

Network & internet security is the burning question of today's world and they are deeply related to each other for secure successful data transmission. Network security approach is totally based on the concept of network security services. In this paper, a new system of network security service is implemented which is more secure than conventional network security services. This technique is mainly deals with two essential network security services, one is user authentication and other is data confidentiality. For user authentication this paper introduces Graphical Username & Voice Password approaches which provides better security than conventional username & password authentication process. In data confidentiality section this paper introduces two layer private key for both message encryption & decryption which is mainly applicable on 8 bit plain text data. This paper also provides the hints of introducing other two network security services (integrity and non-repudiation) as a future work.
A tight bound on the speed-up through storage for quickest multi-commodity flows
Venue: arXiv cs.DS 2014
Year: 2014

Multi-commodity flows over time exhibit the non-intuitive property that letting flow wait can allow us to send flow faster overall. Fleischer and Skutella (IPCO~2002) show that the speed-up through storage is at most a factor of~$2$, and that there are instances where the speed-up is as large as a factor of~$4/3$. We close this gap by presenting a family of instances for which the speed-up factor through storage converges to~$2$.
Local Doubling Dimension of Point Sets
Venue: arXiv cs.CG 2014
Year: 2014

We introduce the notion of t-restricted doubling dimension of a point set in Euclidean space as the local intrinsic dimension up to scale t. In many applications information is only relevant for a fixed range of scales. We present an algorithm to construct a hierarchical net-tree up to scale t which we denote as the net-forest. We present a method based on Locality Sensitive Hashing to compute all near neighbours of points within a certain distance. Our construction of the net-forest is probabilistic, and we guarantee that with high probability, the net-forest is supplemented with the correct neighbouring information. We apply our net-forest construction scheme to create an approximate Cech complex up to a fixed scale; and its complexity depends on the local intrinsic dimension up to that scale.