The perceptions and decisions of individuals on social networks are deeply rooted in their intrinsic beliefs, which makes it possible to infer social beliefs from user behavior and message interactions. While existing research models these interactions as graphs and learns their representations, interpretability remains a significant challenge. In real-world scenarios, the interpretation of beliefs is nested within subject scopes of different granularity (such as topics and locations), posing additional challenges for belief discovery. In this paper, we introduce the Interpretable Graph Auto-Encoder Tree (IGAT), a novel end-to-end framework that jointly encodes hierarchical subject scopes and corresponding beliefs as a unified, interpretable hierarchical representation. IGAT integrates the interpretable hierarchy of Model Trees with disentangled representation learning models. We propose a differentiable Slice Mechanism to dynamically optimize internal node splitting and jointly train a leaf model to learn disentangled belief subspaces. The aggregation of these subspaces yields a unified representation, offering interpretations for both subjects and beliefs. Experimental evaluations on three real-world Twitter datasets show that IGAT achieves a consistent improvement of 1.49%-5.61% in F1-score, accuracy, and purity in the belief discovery task, as well as its effectiveness in various downstream analytical applications.

The landscape of high-performance computing (HPC) has been expanding with new technologies and increased system complexity. For hardware, this trend is driven by technological inventions increasing computing power capabilities while taming cost metrics. For applications, we are witnessing increasing growth in algorithms' complexity to accommodate constantly expanding data sizes and take full advantage of increasingly complex processing and storage characteristics. Successfully handling this expansion and maintaining performance and efficiency on adequate levels requires software that matches the emerging hardware and system innovations and can address concerns arising from evolving and new paradigms. An example of the evolving paradigms is heterogeneity-one of the most challenging properties of emerging parallel, distributed, and edge computing platforms. An appealing example of the new paradigms is a vigorous expansion of artificial intelligence (AI) and machine learning (ML) methods that have become pervasive in solving the most demanding problems across many science and engineering disciplines. Also, the approaching end of Moore's Law scaling requires exciting but complex innovations and advances in HPC hardware/software environments that need to be matched by advances in algorithms and software systems to meet the demands of the applications.

The naming game (NG) is a classic model for studying the emergence and evolution of language within a population. In this article, we extend the traditional NG model to encompass multiple committed opinions and investigate the system dynamics on the complete graph with an arbitrarily large population and random networks of finite size. For the fully connected complete graph, the homogeneous mixing condition enables us to use mean-field theory to analyze the opinion evolution of the system. However, when the number of opinions increases, the number of variables describing the system grows exponentially. To mitigate this, we focus on a special scenario where the largest group of committed agents competes with a motley of committed groups, each of which is smaller than the largest one, while initially, most of uncommitted agents hold one unique opinion. This scenario is chosen for its recurrence in diverse societies and its potential for complexity reduction by unifying agents from smaller committed groups into one category. Our investigation reveals that when the size of the largest committed group reaches the critical threshold, most of uncommitted agents change their beliefs to this opinion, triggering a phase transition. Further, we derive the general formula for the multiopinion evolution using a recursive approach, enabling investigation into any scenario. Finally, we employ agent-based simulations to reveal the opinion evolution and dominance transition in random graphs. Our results provide insights into the conditions under which the dominant opinion emerges in a population and the factors that influence these conditions.

In social sciences, simulating opinion dynamics to study the ways in which the interplay between homophily and influence leads to the formation of echo chambers is of great importance. Given the wide variety of empirical systems involving the grouping of communities based upon local attribute consensus, simulating and analyzing such dynamics is highly relevant in many other fields as well. As such, in this paper we investigate echo chambers by implementing a unique social game in which we spawn in a large number of agents, each assigned one of the two opinions on an issue and a finite amount of influence in the form of a game currency. Agents attempt to have an opinion that is a majority at the end of the game, to obtain a reward also paid in the game currency. At the beginning of each round, a randomly selected agent is selected, referred to as a speaker. The second agent is selected in the radius of speaker influence (which is a set subset of the speaker’s neighbors) to interact with the speaker as a listener. In this interaction, the speaker proposes a payoff in the game currency from their personal influence budget to persuade the listener to hold the speaker’s opinion in future rounds until chosen listener again. The listener can either choose to accept or reject this payoff to hold the speaker’s opinion for future rounds. The listener’s choice is informed only by their estimate of global majority opinion through a limited view of the opinions of their neighboring agents. We show that the influence game leads to the formation of ”echo chambers,” or homogeneous clusters of opinions. We also investigate various scenarios to disrupt the creation of such echo chambers, including the introduction of resource disparity between agents with different opinions, initially preferentially assigning opinions to agents, and the introduction of committed agents, who never change their initial opinion.

We focus on organizational structures in covert networks, such as criminal or terrorist networks. Their members engage in illegal activities and attempt to hide their association and interactions with these networks. Hence, data about such networks are incomplete. We introduce a novel method of rewiring covert networks parameterized by the edge connectivity standard deviation. The generated networks are statistically similar to themselves and to the original network. The higher-level organizational structures are modeled as a multi-layer network while the lowest level uses the Stochastic Block Model. Such synthetic networks provide alternative structures for data about the original network. Using them, analysts can find structures that are frequent, therefore stable under perturbations. Another application is to anonymize generated networks and use them for testing new software developed in open research facilities. The results indicate that modeling edge structure and the hierarchy together is essential for generating networks that are statistically similar but not identical to each other or the original network. In experiments, we generate many synthetic networks from two covert networks. Only a few structures of synthetics networks repeat, with the most stable ones shared by 18% of all synthetic networks making them strong candidates for the ground truth structure.

Abstract We consider two new problems regarding the impact of edge addition or removal on the modularity of partitions (or community structures) in a network. The first problem seeks to add edges to enforce that a desired partition is one partition that maximizes modularity. The second problem seeks to find the sparsest representation of a network that has the same partition with maximum modularity as the original network. We present integer programming formulations, a row generation algorithm, and heuristic algorithms to solve these problems. Further, we demonstrate a counter‐intuitive behavior of modularity that makes the development of heuristics for general networks difficult. We then present results on a selection of social and illicit networks from the literature.

PPAM is a biennial series of international conferences dedicated to exchanging ideas between researchers involved in parallel and distributed computing, including theory and applications, as well as applied and computational mathematics.Twelve previous events have been held in different universities in Poland since 1994, when the first PPAM took place in Czestochowa.Thus, the event in Bialystok was an opportunity to celebrate the 25th anniversary of PPAM.The focus of PPAM 2019 was on models, algorithms, and software tools that facilitate efficient and convenient use of modern parallel and distributed computing systems, as well as on large-scale modern applications, including advances in machine learning and artificial intelligence.This meeting gathered more than 170 participants from 26 countries.The accepted papers were presented at the regular tracks of the PPAM 2019 conference and during the workshops.With each submission evaluated by at least three reviewers, a strict reviewing process resulted in the acceptance of 91 contributed papers for publication in the conference proceedings, while approximately 43% of the submissions were rejected.The Program Committee selected 41 papers for presentation in the regular conference track, resulting in an acceptance rate of about 46%.Based on the review results, 10 papers (11% of submissions) were selected for a special journal issue.Besides quality, another important criterion for selection was each paper's contribution to the thematic consistency of the issue.The focus of this special issue is on algorithmic advancements in matching the software properties to parallel architecture, including GPU accelerators and clusters.These advancements are crucial for successfully parallelizing such complex applications as simulating geophysical flows, solving ordinary differential equations (ODEs), structural analysis of nuclear reactor containment buildings, solving generalized eigenvalue problems, modeling of material science phenomena, and others.A complementary topic of this issue is advances in run-time systems since increasing levels of parallelism in multi-and many-core chips and the emerging heterogeneity of computational resources coupled with energy, resilience, and data movement constraints radically increase the importance of efficient run-time scheduling and execution control.After the conference, the Program Committee invited the authors of selected papers to submit revised and extended versions of their works.These new versions were reviewed independently again by at least three reviewers.Finally, nine contributions were accepted for publication.They are summarized below.Paper [1] focuses on the accurate assembly of the system matrix, which is an essential step in any code that solves partial differential equations on a mesh.This step can become costly in multigrid codes requiring cascades of matrices that depend upon each other, or dynamic adaptive mesh refinement.To reduce the time to solution, the authors propose that these constructions can be performed concurrently with the multigrid cycles.Furthermore, they desynchronize the assembly from the solution process.This non-trivial increase in the concurrency level improves the scalability.As assembly routines are notoriously memory-and bandwidth-demanding, the final algorithmic enhancement uses a hierarchical, lossy compression scheme that brings the memory footprint down aggressively even when the system matrix entries carry little information or are not yet available with high accuracy.An efficient algorithm for the parallel solution of indefinite saddle point systems with iterative solvers based on the Golub-Kahan bidiagonalization is presented in Reference [2].Such systems arise in many application fields, for example, in structural mechanics.A scalability study of the generalized solver shows improved performance for the two-dimensional (2D) Stokes equations compared to previous works.Furthermore, the authors investigate the performance of different parallel inner solvers in the outer Golub-Kahan iteration for a three-dimensional (3D) Stokes problem.When the number of cores is increasing for a fixed problem size, the solver exhibits good speedups of up to 50% with the 1024 cores.For the tests in which the problem size grows while the workload in each core stays constant, the performance of the solver scales almost linearly with the increase in the number of cores. Paper [3] proposes a locality optimization technique for the parallel solution on GPUs of large systems of ODEs by explicit one-step methods.This technique is based on tiling across the stages of a one-step method and is enabled by a special structure of the class of ODE systems-with the limited access distance.The paper focuses on increasing the range of access distances for which the tiling technique can provide a speedup

The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.

Online social media provides massive open-ended platforms for users of a wide variety of backgrounds, interests, and beliefs to interact and debate, facilitating countless information cascades across many subjects. With numerous unique voices being lent to the ever-growing information stream, it is essential to consider the question: how do the many types of conversations within an information cascade characterize the process as a whole? In this paper we analyze the underlying features of the dynamics of communication, and use those features to explain the inherent properties of the encompassing information cascade. Utilizing "microscopic" trends to describe "macroscopic" phenomena, we set a paradigm for analyzing information dissemination through the individual user interactions that sprout from a source topic, instead of trying to interpret the emergent patterns themselves. This paradigm yields a set of unique tools for a myriad of application in the field of information cascade analysis: from topic classification of sources to time-series forecasting. We use these tools in a 88-million-row dataset for Reddit to show their conceptual effectiveness and accuracy when compared to the ground truth.

Time-based habitual behavior is exhibited in humans globally. Given that sleep has such an innate influence on our daily activities, modeling the patterns of the sleep cycle in order to understand the extent of its impact allows us to also capture stable behavioral features that can be utilized for predictive measures. In this paper we show that patterns of temporal preference are consistent and resilient across users of several real-world datasets. Furthermore, we integrate those patterns into large-scale agent-based models to simulate the activity of users in the involved datasets to validate predictive accuracy. Following simulations reveal that incorporating clustering features based on time-based behavior into agent-based models not only result in a significant decrease in computational overhead, but also result in predictive accuracy comparable to the baseline models.

in Lublin, Poland.PPAM is a biennial series of international conferences dedicated to exchanging ideas between researchers involved in parallel and distributed computing, including theory and applications, as well as applied and computational mathematics.The focus of PPAM 2017 was on models, algorithms, and software tools that facilitate efficient and convenient use of modern parallel and distributed computing systems, as well as on large-scale applications, including data-intensive and machine learning problems.

We study community detection in criminal networks and address the problem caused by intentionally hidden edges which hinder the performance of community detection. We make use of link prediction to demonstrate how the community structure of a network can be better identified by augmenting it with edges. We demonstrate the value of this method by showing this method delivers us better quality communities for real life drug trafficking networks. We discuss also the limitations of the approach, and importance of community detection for investigating of criminal networks.

Previous work has shown that selectivity based on opinions and values of attributes is an important tie-formation mechanism in human social networks. Less well-known is how selectivity influences the formation and composition of whole groups in which interactions extend beyond the dyads. To address this question, we use data from the NetSense study consisting of a multi-layer (nomination, communication, co-location) network of university students. We examine how group formation differs from tie-formation in terms of the role of selectivity based on opinions and attributes. In addition, we show how levels of such selectivity varies between groups formed to meet different needs.

To study the detailed effects of social media consumption on personal opinion dynamics, we gather self reported survey data on the volume of different media types an individual must consume before forming or changing their opinion on a subject. We then use frequent pattern mining to analyze the data for common groupings of responses with respect to various media types, sources, and contexts. We show that in general individuals tend to perceive their behavior to be consistent across many variations in these parameters, while further detail shows various common parameter groupings that indicate response changes as well as small groups of individuals that tend to be consistently more easily swayed than the average participant.

In this paper, we study the interaction patterns among university students whose interactions are recorded in an aligned multilayer social network. One layer of this network represents the smartphone communications, including calls and text messages. The other layer represents face-to- face interactions. We analyze this multilayer network to find whether communication and face-to- face interactions are correlated, and what impact the aging, that is the growing over time familiarity of each node with its peers, has on students' interaction patterns. We also investigate to what extent the academic year structure and external events, such as holidays, affect the network and the interactions between the nodes, and how the individual's communication pattern profile varies as a function of the node's degree and intensity of its interactions. The results that we obtained shed a light on how students' interaction patterns are impacted by the structure of a social network, its age, and social profiles of its nodes.

Limited battery capacity has been the main bottleneck for smartphones. Users are required to charge their smartphones frequently to keep them alive. Access to a charging facility, however, may not be possible especially when users are outside. This has caused users to charge their devices at every opportunity with as much power as possible. While this results in overcharging of devices unnecessarily, it might have brought an opportunity for the realization of power sharing among mobile devices. In this paper, we introduce the concept of crowdcharging which aims to provide mobile users with ubiquitous power access through crowdsourcing. We first discuss the feasibility of crowdcharging from users' perspective and present some analysis and survey results showing the interest and need. We then look at the software and hardware challenges to build such a system. To this end, we have developed a mobile app that builds a mobile social network environment among the users and manages the entire process of power sharing between the mobile devices. We present the software implementation details using P2P wireless energy sharing and provide initial lab results with actual wireless charging hardware.

News reports shape the public perception of the critical social, political, and economical events around the world. Yet, the way in which emergent phenomena are reported in the news makes the early prediction of such phenomena a challenging task. We propose a scalable community-based probabilistic framework to model the spreading of news about events in online media. Our approach exploits the latent community structure in the global news media and uses the affiliation of the early adopters with a variety of communities to identify the events widely reported in the news at the early stage .of their spread. The time complexity of our approach is linear in the number of news reports. It is also amenable to efficient parallelization. To demonstrate these features, the inference algorithm is parallelized for message passing paradigm and tested on the Rensselaer Polytechnic Institute Advanced Multiprocessing Optimized System, one of the fastest Blue Gene/Q supercomputers in the world. Thanks to the community-level features of the early adopters, the model gains an improvement of 20% in the early detection of the most massively reported events compared with the feature-based machine learning algorithm. Its parallelization scheme achieves orders of magnitude speedup.

Fueled by users' demand, mobile devices are becoming more complex, increasing their power requirements. However, the battery technology is advancing slower than demand which results in shrinking battery lives (i.e., currently around a day). Hence, users need to charge their devices frequently, mostly by tethering them to a cord. Anxiety of losing power in the middle of a critical task during which users may not have access to charging facilities have increased interest in opportunistic charging with the aim of keeping the devices with as much power as possible. Recently power sharing technologies and gadgets have emerged enabling harvesting power from other mobile devices in the user's vicinity. In this paper, we discuss the energy sharing in mobile social networks whose nodes are human-carried mobile devices operating on batteries. We investigate the limits of power sharing among mobile devices by analyzing their current charging patterns and the social (i.e., close-proximity) interactions between the people carrying these devices. Moreover, we propose an energy sharing model by pairing the nodes in a mobile network into power buddies. Simulation results show that a typical application scenario of energy sharing among power buddies provides a remarkable amount of saving in the utilization of power available in the entire network.

Algorithmic advances for parallel architecturesThis special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected papers presented at the 11th International Conference on Parallel Processing and Applied Mathematics, PPAM 2015, which was held on September 6 to 9, 2015, in Krakow, Poland.PPAM is a biennial series of international conferences dedicated to exchanging ideas between researchers involved in parallel and distributed computing, including theory and applications, as well as applied and computational mathematics.The focus of PPAM 2015 was on models, algorithms, and software tools that facilitate efficient and convenient use of modern parallel and distributed computing systems, as well as on large-scale applications, including data-intensive problems.PPAM 2015 was organized by the Department of Computer and Information Science of the Czestochowa University of Technology together with the AGH University of Science and Technology, under the patronage of the Committee of Informatics of the Polish Academy of Sciences, in cooperation with the ICT COST Action IC1305 "Network for Sustainable Ultrascale Computing (NESUS)."This meeting gathered more than 190 participants from 33 countries.A strict reviewing process, with each submission reviewed at least three times, resulted in acceptance of 111 contributed papers with the acceptance rate of 57%.The accepted papers were presented at the regular tracks of the PPAM 2015 conference, as well as during the workshops that were important and integral parts of the PPAM 2015 meeting.Based on the results of the reviews, selected papers were recommended for a special journal issue.Besides quality, another important goal that influenced the paper selection was a maximum possible thematic consistency of the issue.The focus of this special issue is on algorithmic advances to better match the software properties to the targeted parallel architecture.These advances vary from general, like increasing potential reuse of a part of computation, to specific for a particular architecture, eg, using GPUs or with multi-core and many-core processors, or specific applications, such as spherical Delaunay triangulations, or visualization of complex networks.The authors were contacted after the conference and invited to submit revised and extended versions of their papers.These new versions were reviewed independently by three reviewers.Finally, nine contributions were accepted for publication.They are summarized below.Paper [1] focuses on LU factorization, which is a recurrent operation in scientific and engineering applications used to solve linear systems.In particular, the authors adapt the Gauss-Huard algorithm that has been introduced as an efficient solution for modern platforms equipped with accelerators to improve reusing of computations in this algorithm.This approach was evaluated on the solution of Lyapunov matrix equations via the LRCF-ADI method and validated on three benchmarks.In future work, the authors plan to design a heuristic for choosing the optimal block size and to integrate their solution with the mixed precision techniques to further accelerate the Lyapunov solver.An efficient algorithm for solving dense symmetric indefinite systems on GPUs is presented in the work of Baboulin et al. [2].The critical challenge on these types of computations on hybrid CPU/GPU is to keep to minimum the expensive data transfer and synchronization between the CPU and GPU, or within the GPU.The algorithmic advances here included selecting the solver using iterative refinements and the factorization without pivoting.This approach was then combined with the preprocessing technique based on Random Butterfly Transformations and with the mixed-precision algorithm.The authors demonstrated that an efficient solution can be obtained by avoiding the pivoting and using the lower precision arithmetic.The validation was made using an application in acoustics studied in this paper.

We study a unique behavioral network data set (based on periodic surveys and on electronic logs of dyadic contact via smartphones) collected at the University of Notre Dame. The participants are a sample of members of the entering class of freshmen in the fall of 2011 whose opinions on a wide variety of political and social issues and activities on campus were regularly recorded — at the beginning and end of each semester — for the first three years of their residence on campus. We create a communication activity network implied by call and text data, and a friendship network based on surveys. Both networks are limited to students participating in the NetSense surveys. We aim at finding student traits and activities on which agreements correlate well with formation and persistence of links while disagreements is highly correlated with non-existence or dissolution of links in the two social networks that we created. Using statistical analysis and machine learning, we observe several traits and activities displaying such correlations, thus being of potential use to predict social network evolution.

WiFi offloading has been exploited as a quick and viable solution to decrease the burden on cellular networks. In this paper, we study the problem of deploying new WiFi access points (AP) in a city-wide area for offloading purposes. Different than previous work which look at the problem only from operator's perspective and targets the maximization of offloaded traffic volume, we approach the problem by integrating the user perspective as well. We propose a new AP deployment scheme that aims to increase average individual user satisfaction while still achieving high offloaded total data traffic volume from all users. As the simulation results demonstrate, the proposed approach can achieve more user level satisfaction compared to other algorithms that only target offloaded traffic maximization while keeping operator's benefit from offloading close to others.

The increasing interest of researchers in service oriented architecture (SOA) for wireless sensor networks (WSNs) is opening new unexplored venues in the field of WSNs. In service oriented systems, services are configured and composed of various other services and thus perform complex tasks. In such composite services, the geospatial locations of services and their coverage is of vital importance as they signify the geospatial relevance of the service to the area of interest to the user. In this paper, we present a service-oriented system for WSNs that is capable of performing service configuration under geospatial and relevancy constraints. We present and evaluate “Cost Based Model (CBM)” and “Gain Based Model (GBM)” approaches to capture the relevancy of services hosted on WSN nodes in composite service configuration. The system is resilient to failures and can operate in manual or autonomous recovery modes. The system supports three service configuration methods namely, distributed, centralized and hybrid. Furthermore, we present a novel emulation mechanism for testing the performance of our proposed relevancy models and show that our system efficiently configures services.

There is a need for robust networks in all environments including austere ones. The prime example is Delay Tolerant Networks (DTN) that are subject to a growing body of research. These networks support applications used by the military and first responders, especially in emergency situations. Securing a DTN is not a trivial undertaking due to node mobility and the ADHOC method in which nodes communicate. Here, we propose a distributed trust management scheme to secure this class of networks with many of the underlying principles applicable to the larger class of Mobile ADHOC Networks (MANET). The scheme employs erasure coding not only to increase delivery rate in a DTN but also to infer the trustworthiness of the nodes along all paths that deliver a message segments to the destination. The proposed approach enables us to decide when the destination node should stop waiting for additional segments and instead request message retransmission. Moreover, even after the message is recreated successfully, additional segments received enable the destination to collect precious trust information about the nodes involved in delivery of these segments. We show how distributing this trust information identifies compromised nodes.

It has been shown in this paper that simplistic Bag of Words (BoW) lexicon methods for sentiment polarity assignment with ensemble classifiers are much faster than a supervised approach to sentiment classification while yielding similar accuracy. BoW methods also proved to be efficient and fast across all examined datasets. Moreover, a new approach to lexicon extraction that can be successfully used for sentiment polarity assignment is presented in the paper. It has been shown that accuracy obtained from such lexicons outperforms other lexicon based approaches.

Modularity is widely used to effectively measure the strength of the disjoint community structure found by community detection algorithms. Although several overlapping extensions of modularity were proposed to measure the quality of overlapping community structure, there is lack of systematic comparison of different extensions. To fill this gap, we overview overlapping extensions of modularity to select the best. In addition, we extend the Modularity Density metric to enable its usage for overlapping communities. The experimental results on four real networks using overlapping extensions of modularity, overlapping modularity density, and six other community quality metrics show that the best results are obtained when the product of the belonging coefficients of two nodes is used as the belonging function. Moreover, our experiments indicate that overlapping modularity density is a better measure of the quality of overlapping community structure than other metrics considered.

Collaborative filtering is a fundamental building block in many recommender systems. While most of the existing collaborative filtering methods focus on explicit, multi-class settings (e.g., 1-5 stars in movie recommendation), many real-world applications actually belong to the one-class setting where user feedback is implicitly expressed (e.g., views in news recommendation and video recommendation). The main challenges in such one-class setting include the ambiguity of the unobserved examples and the sparseness of existing positive examples.

The paper presents a new model for crowd-sensing applications, where humans are used as the sensing sources to report information regarding the physical world. In contrast to previous work on the topic, we consider a model where the sources in question are polarized. Such might be the case, for example, in political disputes and in situations involving different communities with largely dissimilar beliefs that color their interpretation and reporting of physical world events. Reconstructing accurate ground truth is more complicated when sources are polarized. The paper describes an algorithm that significantly improves the quality of reconstruction results in the presence of polarized sources. For evaluation, we recorded human observations from Twitter for four months during a recent Egyptian uprising against the former president. We then used our algorithm to reconstruct a version of events and compared it to other versions produced by state of the art algorithms. Our analysis of the data set shows the presence of two clearly defined camps in the social network that tend of propagate largely disjoint sets of claims (which is indicative of polarization), as well as third population whose claims overlap subsets of the former two. Experiments show that, in the presence of polarization, our reconstruction tends to align more closely with ground truth in the physical world than the existing algorithms.

In this paper, we first discuss the definition of modularity (Q) used as a metric for community quality and then we review the modularity maximization approaches which were used for community detection in the last decade. Then, we discuss two opposite yet coexisting problems of modularity optimization; in some cases, it tends to favor small communities over large ones while in others, large communities over small ones (so-called the resolution limit problem). Next, we overview several community quality metrics proposed to solve the resolution limit problem and discuss Modularity Density (Qds), which simultaneously avoids the two problems of modularity. Finally, we introduce two novel fine-tuned community detection algorithms that iteratively attempt to improve the community quality measurements by splitting and merging the given network community structure. The first one, referred to as Fine-tuned , is based on modularity (Q), while the second is based on Modularity Density (Qds) and denoted as Fine-tuned . Then, we compare the greedy algorithm of modularity maximization (denoted as Greedy ), Fine-tuned , and Fine-tuned on four real networks, and also on the classical clique network and the LFR benchmark networks, each of which is instantiated by a wide range of parameters. The results indicate that Fine-tuned Qdsis the most effective among the three algorithms discussed. Moreover, we show that Fine-tuned Qdscan be applied to the communities detected by other algorithms to significantly improve their results.

Overlay network topology together with peer/data organization and search algorithm are the crucial components of unstructured peer-to-peer (P2P) networks as they directly affect the efficiency of search on such networks. Scale-free (power-law) overlay network topologies are among structures that offer high performance for these networks. A key problem for these topologies is the existence of hubs, nodes with high connectivity. Yet, the peers in a typical unstructured P2P network may not be willing or able to cope with such high connectivity and its associated load. Therefore, some hard cutoffs are often imposed on the number of edges that each peer can have, restricting feasible overlays to limited or truncated scale-free networks. In this paper, we analyze the growth of such limited scale-free networks and propose two different algorithms for constructing perfect scale-free overlay network topologies at each instance of such growth. Our algorithms allow the user to define the desired scale-free exponent ( γ). They also induce low communication overhead when network grows from one size to another. Using extensive simulations, we demonstrate that these algorithms indeed generate perfect scale free networks (at each step of network growth) that provide better search efficiency in various search algorithms than the networks generated by the existing solutions.

Information propagation in social media depends not only on the static follower structure but also on the topic-specific user behavior. Hence novel models incorporating dynamic user behavior are needed. To this end, we propose a model for individual social media users, termed a genotype. The genotype is a per-topic summary of a user's interest, activity and susceptibility to adopt new information. We demonstrate that user genotypes remain invariant within a topic by adopting them for classification of new information spread in large-scale real networks. Furthermore, we extract topic-specific influence backbone structures based on information adoption and show that they differ significantly from the static follower network. When employed for influence prediction of new content spread, our genotype model and influence backbones enable more than 20% improvement, compared to purely structural features. We also demonstrate that knowledge of user genotypes and influence backbones allow for the design of effective strategies for latency minimization of topic-specific information spread.

The proliferation of social media has the potential for changing the structure and organization of the web. In the past, scientists have looked at the web as a large connected component to understand how the topology of hyperlinks correlates with the quality of information contained in the page and they proposed techniques to rank information contained in web pages. We argue that information from web pages and network data on social relationships can be combined to create a personalized and socially connected web. In this paper, we look at the web as a composition of two networks, one consisting of information in web pages and the other of personal data shared on social media web sites. Together, they allow us to analyze how social media tunnels the flow of information from person to person and how to use the structure of the social network to rank, deliver, and organize information specifically for each individual user. We validate our social ranking concepts through a ranking experiment conducted on web pages that users shared on Google Buzz and Twitter.

SUMMARY This article describes a technique for path unfolding for conditional branches in parallel programs executed on clusters. Unfolding paths following control structures makes it possible to break the control dependencies existing in the code and consequently to obtain a high degree of parallelism through the use of idle CPUs. The main challenge of this technique is to deal with sequences of control statements. When a control statement appears in a path after a branch, a new conditional block needs to be opened, creating a new code split before the previous one is resolved. Such subsequent code splits increase the cost of speculation management, resulting in reduced profits. Several decision techniques have been developed for improving code splitting and speculation efficiency in single machine architecture. The main contribution of this paper is to apply such techniques to a cluster of single processor systems and evaluate them in such an environment. Our results demonstrate that code splitting in conjunction with branch speculation and the use of statistical information improves the performance measured by the number of processes executed in a time unit. This improvement is particularly significant when the parallelized programs contain iterative structures in which conditions are repeatedly executed. Copyright © 2012 John Wiley & Sons, Ltd.

Modeling of the mobility patterns arising in computer networks requires a compact and faithful representation of the mobility data collected from observations and measurements of the relevant network applications. This data can range from the information on the mobility of the agents that are being monitored by a wireless network to mobility information of nodes in mobile network applications. In this paper, we examine the use of probabilistic context-free grammars as the modeling framework for such data. We present a fast algorithm for deriving a concise probabilistic context-free grammar from the given training data. The algorithm uses an evaluation metric based on Bayesian formula for maximizing grammar a posteriori probability given the training data. We describe the application of this algorithm in two mobility modeling domains: 1) recognizing mobility patterns of monitored agents in different event data sets collected by sensor networks, and 2) modeling and generating node movements in mobile networks. We also discuss the model's performance in simulations utilizing both synthetic and real-world mobility traces.

Service modeling and service composition are software architecture paradigms that have been used extensively in web services where there is an abundance of resources. They mainly capture the idea that advanced functionality can be realized by combining a set of primitive services provided by the system. Many efforts in web services domain focused on detecting the initial composition, which is then followed for the rest of service operation. In sensor networks, however, communication among nodes is error-prone and unreliable, while sensor nodes have constrained resources. This dynamic environment requires a continuous adaptation of the composition of a complex service. In this paper, we first propose a graph-based formulation for modeling sensor services that maps to the operational model of sensor networks and is amenable to analysis. Based on this model, we formulate the process of sensor service composition as a cost-optimization problem and show that it is NP-complete. Two heuristic methods are proposed to solve the composition problem: the top-down and the bottom-up approaches. We discuss centralized and distributed implementations of these methods. Finally, using ns-2 simulations, we evaluate the performance and overhead of our proposed methods.

Diversified ranking is a fundamental task in machine learning. It is broadly applicable in many real world problems, e.g., information retrieval, team assembling, product search, etc. In this paper, we consider a generic setting where we aim to diversify the top-k ranking list based on an arbitrary relevance function and an arbitrary similarity function among all the examples. We formulate it as an optimization problem and show that in general it is NP-hard. Then, we show that for a large volume of the parameter space, the proposed objective function enjoys the diminishing returns property, which enables us to design a scalable, greedy algorithm to find the near-optimal solution. Experimental results on real data sets demonstrate the effectiveness of the proposed algorithm.

Routing in delay tolerant networks is a challenging problem due to the intermittent connectivity between nodes resulting in the frequent absence of end-to-end path for any source-destination pair at any given time. Recently, this problem has attracted a great deal of interest and several approaches have been proposed. Since Mobile Social Networks (MSNs) are increasingly popular type of Delay Tolerant Networks (DTNs), making accurate analysis of social network properties of these networks is essential for designing efficient routing protocols. In this paper, we introduce a new metric that detects the quality of friendships between nodes accurately. Utilizing this metric, we define the community of each node as the set of nodes having close friendship relations with this node either directly or indirectly. We also present Friendship-Based Routing in which periodically differentiated friendship relations are used in forwarding of messages. Extensive simulations on both real and synthetic traces show that the introduced algorithm is more efficient than the existing algorithms.

Routing in delay tolerant networks (DTNs) is challenging due to their unique characteristics of intermittent node connectivity. Different protocols (single-copy, multi-copy, erasure-coding-based etc.) utilizing store-carry-and-forward paradigm are proposed to achieve routing of messages in such environments by opportunistic message exchanges between nodes that are in the communication range of each other. The sparsity and distributed nature of these networks together with the lack of stable connectivity between source destination pairs make these networks vulnerable to malicious nodes which might attempt to learn the content of the messages being routed between the nodes. In this paper, we consider DTNs in which malicious nodes are present, to which we refer to as compromised DTNs. We discuss and analyze the effects of presence of malicious nodes in the compromised DTN on routing of messages. We propose a two period routing approach which aims to achieve desired delivery ratio by a given delivery deadline in presence of malicious nodes. Our results show that, with proper parameter setting, the desired delivery ratio by a given delivery deadline can be achieved most of the time by the proposed method.

Data access is an important issue in Delay Tolerant Networks (DTNs), and a common technique to improve the performance of data access is cooperative caching. However, due to the unpredictable node mobility in DTNs, traditional caching schemes cannot be directly applied. In this paper, we propose DAC, a novel caching protocol adaptive to the challenging environment of DTNs. Specifically, we exploit the social community structure to combat the unstable network topology in DTNs. We propose a new centrality metric to evaluate the caching capability of each node within a community, and solutions based on this metric are proposed to determine where to cache. More importantly, we consider the impact of the contact duration limitation on cooperative caching, which has been ignored by the existing works. We prove that the marginal caching benefit that a node can provide diminishes when more data is cached. We derive an adaptive caching bound for each mobile node according to its specific contact patterns with others, to limit the amount of data it caches. In this way, both the storage space and the contact opportunities are better utilized. To mitigate the coupon collector's problem, network coding techniques are used to further improve the caching efficiency. Extensive trace-driven simulations show that our cooperative caching protocol can significantly improve the performance of data access in DTNs.

At CPSWeek 2011, the authors presented a demonstration of Apollo, a fact-finder for participatory sensing that ranks archived human-centric and sensor data by credibility. The current demonstration significantly extends our previous work by allowing Apollo to operate on live streaming data; in this case, live Twitter feeds. As the role of humans as sensors increases in emerging sensing applications, a principled approach becomes necessary to address the problem of ascertaining the veracity of sources and observations made by them. Participatory and social sensing applications may use potentially unreliable or unverified sources, such as a phone-based sensing application that grows virally in a large un-vetted population, a disaster-response application, where conflicting damage assessment reports may come from large numbers of different volunteers, or a military application, where friendly observers at a remote location may make hard-to-verify claims about local events. Apollo analyzes noisy data that increasingly plagues human-centric sensing to determine which items of information are more likely to be true.

Psychometric AI is a type of AI distinguished by the pursuit of intelligent systems able to excel on psychometrically validated human-level tests of cognitive abilities. We seek to build a system that solves a specific sub-test within Psychometric AI: the story arrangment test. Items in this test confront the test-taker with a set of jumbed snapshots (whether diagrammatic or otherwise) which must be ordered to tell a coherent story. We propose a dual-process system that combines bottom-up non- or sub-symbolic processing (e.g. neural network-based modelling) with top-down symbolic processing (e.g. deductive reasoning over declarative information represented as formulae in a logical system) for solving these tests of cognitive ability. The top-down process provides the benefits of a traceable proof, but requires a large amount of pre-existing knowledge. The bottom-up technique sacrifices provability and certainty on some problems for speed, but always yields some level of an answer to a given problem. This demonstrates a natural marriage between the two: the bottom-up approach seems especially powerful when used as a form of pre-processing in conjunction with a logic-based approach, because the latter approach would only need to consider a small number of possible orderings of snapshots.

Computational science is placing new demands on optimization algorithms as the size of data sets and the computational complexity of scientific models continue to increase. As these complex models have many local minima, evolutionary algorithms (EAs) are very useful for quickly finding optimal solutions in these challenging search spaces. In addition to the complex search spaces involved, calculating the objective function can be extremely demanding computationally. Because of this, distributed computation is a necessity. In order to address these computational demands, top-end distributed computing systems are surpassing hundreds of thousands of computing hosts; and as in the case of Internet based volunteer computing systems, they can also be highly heterogeneous and faulty. This work examines asynchronous strategies for distributed EAs using simulated computing environments. Results show that asynchronous EAs can scale to hundreds of thousands of computing hosts while being highly resilient to heterogeneous and faulty computing environments, something not possible for traditional distributed EAs which require synchronization. While the simulation not only provides insight as to how asynchronous EAs perform on distributed computing environments with different latencies and heterogeneity, it also serves as a sanity check because live distributed systems require problems with high computation to communication ratios and traditional benchmark problems cannot be used for meaningful analysis due to their short computation times.

Routing in delay tolerant networks (DTN) have attracted a great interest recently. Increasingly popular type of DTNs are mobile social networks (MSN) also called pocket switched networks. Hence, analyzing accurately social network properties has become an important issue in designing efficient routing protocols for MSNs. In this paper, we first introduce a new metric for detecting the quality of friendships accurately. Using the introduced metric, each node defines its friendship community as the set of nodes having close friendship with itself either directly or indirectly. Then, we present Friendship Based Routing in which temporally differentiated friendships are used to make the forwarding decisions of messages. Real trace-driven simulation results show that the introduced algorithm achieves better delivery rate while forwarding fewer messages than the existing algorithms.

This paper introduces a novel method of generating mobility traces based on Probabilistic Context Free Grammars (PCFGs). A PCFG is a generalization of a context free grammar in which each production rule is augmented with a probability with which this production is applied during sentence generation. A concise PCFG can be inferred from the given real world trace collected from the actual mobile node behaviors. The resulting grammar can be used to generate sequences of arbitrary length mimicking the mobile node behavior. This is important when new protocol designs for mobile networks are tested by simulation. In the paper, we describe the methods developed to construct such grammars from training data (mobility history). We also discuss how to generate the synthetic data with an already constructed grammar. We present the experimental results on two real data sets, measuring similarity of the actual traces with the synthetic ones. We compare our grammar based method to a 2-level Markov Model based trace generation method. The results demonstrate that the grammar based approach works as an excellent compression method for the actual data. On many metrics, the synthetic data generated from the PCFG match the training data much better than the one generated by the Markov Model.

Routing in delay tolerant networks (DTNs) in which most of the nodes are mobile and intermittently connected is a challenging problem because of unpredictable node movements and lack of knowledge of future node connections. To ensure reliability against failures and increase the success rate of delivery, erasure coding technique is used to route messages in DTNs. In this paper, we study how the cost of erasure coding based routing protocols can be reduced. Specifically, we analyze the effects of different spraying algorithms, right parameter selection and splitting spraying phase on the cost of message delivery. We also perform simulations to evaluate the proposed approaches and demonstrate that the cost of erasure coding based routing can be reduced considerably with the proposed strategies while maintaining the delivery rate and delay objectives.

Coverage redundancy problem is one of the significant problems in wireless sensor networks. To reduce the energy consumption that arises when the high number of sensors is active, various coverage control protocols (sleep scheduling algorithms) have been proposed. In these protocols, a subset of nodes necessary to maintain sufficient sensing coverage are kept active while the others are put into a sleep mode to reduce the energy consumption. In this paper, we study the coverage redundancy problem in a sensor network where the locations of nodes and the distances between nodes are neither known nor could be easily calculated. We define a neighbor graph as the graph formed by the neighbors of a node and analyze the effect of different levels of connectivity in neighbor graphs on the coverage redundancy of sensor nodes. Moreover, we apply our results to a lightweight deployment-aware scheduling algorithm and demonstrate the improvement in the performance of the algorithm.

There is a significant challenge in designing, optimizing, deploying and managing complex sensor networks over heterogeneous communications infrastructures. The ITA Sensor Fabric addresses these challenges in the areas of sensor identification and discovery, sensor access and control, and sensor data consumability, by extending the message bus model commonly found in commercial IT infrastructures out to the edge of the network. In this paper we take the message bus model further into a semantically rich, model-based design and analysis approach that considers the sensor network and its contained services as a Service Oriented Architecture. We present an application of a hierarchic schema for nested service definitions together with an initial ontology that describes the assets and services deployed in a sensor network infrastructure.

Trust is an important yet complex and little understood aspect of the dyadic relationship between two entities. Trust plays an important role in the formation of coalitions in social networks and in determining how high value of information flows through the network. We present algorithmically quantifiable measures of trust based on communication behavior. We propose that trust results in likely communication behaviors which are statistically different from random communications; detecting these trust-like behaviors allows us to develop a quantitative measure of who trusts whom in the network. We develop algorithms to efficiently compute such behavioral trust and validate these measures on the Twitter network.

In a delay tolerant network (DTN), nodes are connected intermittently and the future node connections are mostly unknown. Since in these networks, a fully connected path from source to destination is unlikely to exist, message delivery relies on opportunistic routing. However, effective forwarding based on a limited knowledge of contact behavior of nodes is challenging. Most of the previous studies looked at only the pairwise node relations to decide routing. In contrast, in this paper, we analyze the correlation between the meetings of each node with other nodes and focus on the utilization of this correlation for efficient routing of messages. We introduce a new metric called conditional intermeeting time, which computes the average intermeeting time between two nodes relative to a meeting with a third node using only the local knowledge of the past contacts. Then, we show how we can utilize the proposed metric on the existing DTN routing protocols to improve their performance. For shortest-path based routing protocols in DTNs, we propose to route messages over conditional shortest paths in which the link cost between nodes are defined by conditional intermeeting times. Moreover, for metric-based forwarding protocols, we propose to use conditional intermeeting time as an additional delivery metric while making forwarding decisions of messages. Our trace-driven simulations on three different datasets show that the modified algorithms perform better than the original ones.

Delay tolerant networks are characterized by the sporadic connectivity between their nodes and therefore the lack of stable end-to-end paths from source to destination. Since the future node connections are mostly unknown in these networks, opportunistic forwarding is used to deliver messages. However, making effective forwarding decisions using only the network characteristics (i.e. average intermeeting time between nodes) extracted from contact history is a challenging problem. Based on the observations about human mobility traces and the findings of previous work, we introduce a new metric called conditional intermeeting time, which computes the average intermeeting time between two nodes relative to a meeting with a third node using only the local knowledge of the past contacts. We then look at the effects of the proposed metric on the shortest path based routing designed for delay tolerant networks. We propose Conditional Shortest Path Routing (CSPR) protocol that routes the messages over conditional shortest paths in which the cost of links between nodes is defined by conditional intermeeting times rather than the conventional intermeeting times. Through trace-driven simulations, we demonstrate that CSPR achieves higher delivery rate and lower end-to-end delay compared to the shortest path based routing protocols that use the conventional intermeeting time as the link metric.

Sensor networks face a number of challenges when deployed in unpredictable environments under dynamic, quickly changeable demands, and when shared by many partners, which is often the case in military and security applications. To partially address these challenges, we present a novel target tracking algorithm that can be deployed on various sensor nodes and invoked dynamically when needed by the presence of targets. We also demonstrate that an auction-based mechanism can be used to provide efficient and localized wireless sensor network congestion management for bursty traffic of abstract services based just on user-assigned priorities to different services and the quality of information provided by the services. We present results from using this auction mechanism to resolve congestion caused by packets from competing target tracking missions.

We present VOGUE, a novel, variable order hidden Markov model with state durations, that combines two separate techniques for modeling complex patterns in sequential data: pattern mining and data modeling. VOGUE relies on a variable gap sequence mining method to extract frequent patterns with different lengths and gaps between elements. It then uses these mined sequences to build a variable order hidden Markov model (HMM), that explicitly models the gaps. The gaps implicitly model the order of the HMM, and they explicitly model the duration of each state. We apply VOGUE to a variety of real sequence data taken from domains such as protein sequence classification, Web usage logs, intrusion detection, and spelling correction. We show that VOGUE has superior classification accuracy compared to regular HMMs, higher-order HMMs, and even special purpose HMMs like HMMER, which is a state-of-the-art method for protein classification. The VOGUE implementation and the datasets used in this article are available as open-source. 1

In this paper, we present a novel multiperiod spraying algorithm for routing in delay-tolerant networks (DTNs). The goal is to minimize the average copy count used per message until the delivery while maintaining the predefined message delivery rate by the given deadline. In each period, some number of additional copies are sprayed into the network, followed by the wait for message delivery. At any time instance, the total number of message copies distributed to the network depends on the urgency of achieving the delivery rate by the given deadline for that message. Waiting for early delivery in the initial periods with a small number of copies in existence decreases the average number of copies sprayed in the network till delivery. We first discuss two- and three-period variants of our algorithm, and then we also give an idea of how the presented approach can be extended to more periods. We present an in-depth analysis of the algorithm and validate the analytical results with simulations. The results demonstrate that our multiperiod spraying algorithm outperforms the algorithms with a single spraying period.

Target tracking is a typical and important cooperative sensing application of wireless sensor networks. We study it in its most basic form, assuming a binary sensing model in which each sensor returns only 1-bit information regarding target's presence or absence within its sensing range. A novel, real-time and distributed target tracking algorithm is introduced. The algorithm is energy efficient and fault tolerant. It estimates the target location, velocity, and trajectory in a distributed and asynchronous manner. The accuracy of the algorithm is analytically derived under an ideal binary sensing model and extensive simulations of ideal, imperfect, and faulty sensing models show that the algorithm achieves good performance. It outperforms other published algorithms by yielding highly accurate estimates of the target's location, velocity, and trajectory.

Volunteer computing grids offer significant computing power at relatively low cost to researchers, while at the same time generating public interest in different scientific projects. However, in order to be used effectively, their heterogeneity, volatility and restrictive computing models must be overcome. As these computing grids are open, incorrect or malicious results must also be handled. This paper examines extending the BOINC volunteer computing framework to allow for asynchronous global optimization as applied to scientific computing problems. The asynchronous optimization method used is resilient to faults and the heterogeneous nature of volunteer computing grids, while allowing scalability to tens of thousands of hosts. A work verification strategy that does not require the validation of every result is presented. This is shown to be able to effectively reduce the need for verification done to less than 30% of the reported results, without degrading the performance of the asynchronous search methods. An asynchronous version of particle swarm optimization (APSO) is presented and com- pared to previously used asynchronous genetic search (AGS) using the MilkyWay@Home BOINC computing project. Both search methods are shown to scale to MilkyWay@Home's current user base, over 75,000 heterogeneous and volatile hosts, something not possible for traditional optimization methods. APSO is shown to provide faster convergence to optimal results while being less sensitive to its search parameters. The verification strategy presented is shown to be effective for both AGS and APSO.

Delay Tolerant Networks (DTNs) are wireless networks in which at any given time instance, the probability of having a complete path from a source to destination is low due to the intermittent connectivity between nodes. Several routing schemes have been proposed for such networks to make the delivery of messages possible despite the intermittent connections. In this paper, in addition to intermittent connectivity which impacts routing most strongly, we also analyze the effects of underlying social structure over the communication network. In a social network, nodes interact in diverse ways so that some nodes meet each other more frequently than others. In the paper, we first propose a new network model to reflect the underlying social structure over the network nodes, then we study the effects of this model on the performance of multi-copy based routing algorithms. We also analyze the performance of routing and validate our analysis with simulations.

This paper studies an auction based allocation of network resources for short-term contracts for heterogeneous network services. The combinatorial winner selection yields the optimal resources allocation in a single-round auction for heterogeneous resources. However, the recurring nature of auction for network services causes least wealthy bidders to exit the auction as they persistently lose under the traditional combinatorial winner selection that focuses only on revenue maximization. Such exits decrease price competition and may cause a collapse of the selling prices and revenues of network service providers. We introduce and evaluate a novel auction based network resource allocation and pricing mechanism for heterogeneous network services. The proposed mechanism prevents collapse of the selling prices and the auctioneer's revenues, stabilizes auction market, and enhances social welfare by allowing larger subset of users to become occasional winners of auction rounds than the traditional combinatorial winner selection does.

One of the most common and important applications of wireless sensor networks is target tracking. We study it in its most basic form, assuming the binary sensing model in which each sensor can return only information regarding target's presence or absence within its sensing range. However, unlike most of traditional approaches to binary sensing, we allow sensors to recognize not only target's range but also a sector within the circular range around it. Examples of such sensors include cameras, infrared sensors, ultrasonic sensors, etc. For simplicity, we assume that either a group of sensors are collocated in a single spot providing 360 degree coverage or a sensor has multiple antennas or camera providing such coverage. A novel, real-time and distributed target tracking algorithm with directional binary sensor networks is proposed. It is an extension of our previous work on omni-directional binary sensor networks. Using simulations, we demonstrate that this new algorithm achieves high performance and outperforms other algorithms by yielding accurate estimates of the target's location. In addition, we discuss the fundamental performance limits and improvement of the tracking performance resulting from providing direction range in addition to a distance range for the algorithm.

Multipath routing can reduce the need for route updates, balance the traffic load and increase the data transfer rate in a wireless sensor network, improving the utilization of the limited energy of sensor nodes. However, previous multiple path routing methods use flooding for route discovery and transmit data with maximum power regardless of need, which results in waste of energy. Moreover, often a serious problem of collisions among multiple paths arises. In this paper, we propose an energy efficient and collision aware (EECA) node-disjoint multipath routing algorithm for wireless sensor networks. With the aid of node position information, the EECA algorithm attempts to find two collision-free routes using constrained and power adjusted flooding and then transmits the data with minimum power needed through power control component of the protocol. Our preliminary simulation results show that ECCA algorithm results in good overall performance, saving energy and transferring data efficiently.

Modern military and civilian surveillance applications should provide end users with the high level representation of events observed by sensors rather than with the raw data measurements. Hence, there is a need for a system that can infer higher level meaning from collected sensor data. We demonstrate that probabilistic context free grammars (PCFGs) can be used as a basis for such a system. To recognize events from raw sensor network measurements, we use a PCFG inference method based on Stolcke (1994) and Chen(1996). We present a fast algorithm for deriving a concise probabilistic context free grammar from the given observational data. The algorithm uses an evaluation metric based on Bayesian formula for maximizing grammar a posteriori probability given the training data. We also present a real-world scenario of monitoring a parking lot and the simulation based on this scenario. We described the use of PCFGs to recognize events in the results of such a simulation. We finally demonstrate the deployment details of such an event recognition system.

Routing protocols for wireless sensor networks (WSN) face three major performance challenges. The first one is an efficient use of bandwidth that minimizes the transfer delay of packets between nodes to ensure the shortest end-to-end delay for packet transmission from source to destination. The second challenge is the ability to maintain data flow around permanent and transient node or link failures ensuring the maximum delivery rate of packets from source to destination. The final challenge is to efficiently use energy while maximizing delivery rate and minimizing end-to-end delay. Protocols that establish a permanent route between source and destination send packets from node to node quickly, but suffer from costly route recalculation in the event of any node or link failures. Protocols that select the next hop at each node on the traversed path suffer from a delay required to make such selection. The way in which a protocol repairs routes determines the number of packets lost by each failure and ultimately affects the energy used for communication. This paper presents a novel family of wireless sensor routing protocols, the self-selecting reliable path routing protocol family (SSRPF), that address all three of the afore-mentioned challenges.

This paper addresses the problem of providing congestion-management for a shared wireless sensor network- based target tracking system. In many large-scale wireless sensor network target tracking scenarios (e.g., a surveillance system for tracking vehicles in urban environments), multiple targets may converge within close proximity of each other. Such scenarios may cause network congestion as nearby sensors attempt to concurrently send updates to a data aggregation point (e.g., base station). We consider the case in which this problem is further complicated by two factors. First, such a large-scale sensor network may very well be deployed to serve multiple target tracking applications with different and dynamic priorities and interests in different (types of) targets. Second, each application will most likely place a different premium on the timeliness of the target information (principally defined by some quality metric) they receive. All the above challenges introduce formidable challenges in providing the expeditious delivery of target information to all prioritized applications. In this paper, we advocate the use of a distributed auction-based approach to locally manage network bandwidth allocation in the described context. We use the Second Price Auction mechanism (to ensure incentive compatibility) in which the congested node acts as the auctioneer and the packets carrying target updates act as bidders. Their bid values are defined by the loss of information utility to the applications associated with the packets. The winning packet receives the current transmission slot of the auctioneer node. We demonstrate through simulation that the resulting auction allocates bandwidth efficiently, maximizing the collective applications' goals, even when the application priorities change dynamically.

Abstract Malleability enables a parallel application's execution system to split or merge processes modifying granularity. While process migration is widely used to adapt applications to dynamic execution environments, it is limited by the granularity of the application's processes. Malleability empowers process migration by allowing the application's processes to expand or shrink following the availability of resources. We have implemented malleability as an extension to the process checkpointing and migration (PCM) library, a user‐level library for iterative message passing interface (MPI) applications. PCM is integrated with the Internet Operating System, a framework for middleware‐driven dynamic application reconfiguration. Our approach requires minimal code modifications and enables transparent middleware‐triggered reconfiguration. Experimental results using a two‐dimensional data parallel program that has a regular communication structure demonstrate the usefulness of malleability. Copyright © 2008 John Wiley & Sons, Ltd.

This paper examines the use of a probabilistic simplex operator for asynchronous genetic search on the BOINC volunteer computing framework. This algorithm is used to optimize a computationally intensive function with a continuous parameter space: finding the optimal fit of an astronomical model of the Milky Way galaxy to observed stars. The asynchronous search using a BOINC community of over 1,000 users is shown to be comparable to a synchronous continuously updated genetic search on a 1,024 processor partition of an IBM BlueGene/L supercomputer. The probabilistic simplex operator is also shown to be highly effective and the results demonstrate that increasing the parents used to generate offspring improves the convergence rate of the search. Additionally, it is shown that there is potential for improvement by refining the range of the probabilistic operator, adding more parents, and generating offspring differently for volunteered computers based on their typical speed in reporting results. The results provide a compelling argument for the use of asynchronous genetic search and volunteer computing environments, such as BOINC, for computationally intensive optimization problems and, therefore, this work opens up interesting areas of future research into asynchronous optimization methods.

Intermittently connected mobile networks, also called delay tolerant networks (DTNs), are wireless networks in which at any given time instance, the probability of having a complete path from a source to destination is low. Several routing algorithms have been proposed for such networks based on control flooding in which there is a fixed number of copies for each message. Although a DTN is delay tolerant by definition, often there is an upper bound imposed on message delivery delay. In this paper, we propose a novel spraying algorithm in which the number of message copies in the network depends on the urgency of meeting the expected delivery delay for that message. The main objective of this algorithm is to give a chance to early delivery with small number of copies in existence, consequently decreasing the average number of copies sprayed in the network. We derive the formula for the optimum borders of periods for spraying for two-period and three-period variants of our algorithm. We also present simulations of the method and compare their results with the analytical ones and observe the good match between them. Furthermore, we demonstrate that time dependent spraying algorithm provides a significant decrease in average copy count per message while preserving the percentage of the messages delivered before the upper bound of the acceptable delay expires.

We study target tracking with wireless sensor networks in its most basic form, assuming a binary sensing model in which each sensor can return only 1-bit information regarding target's presence or absence in its sensing range. A novel, real-time and distributed target tracking algorithm for imperfect binary sensing models is proposed, which is an extension of our previous work on the ideal binary sensing model. The algorithm estimates target's location, velocity and trajectory in a distributed and asynchronous manner. Extensive simulations show that our algorithm achieves high performance and outperforms other algorithms in terms of accuracy of the estimation of target's location, velocity and trajectory.

Use of large-scale heterogeneous computing environments such as computational grids and the Internet has become of high interest to scientific researchers. This is because the increasing complexity of their scientific models and data sets is drastically outpacing the increases in processor speed while the cost of supercomputing environments remains relatively high. However, the heterogeneity and unreliability of these environments, especially the Internet, make scalable and fault tolerant search methods indispensable to effective scientific model verification. The paper introduces two versions of asynchronous master-worker genetic search and evaluates their convergence and performance rates in comparison to traditional synchronous genetic search on both a IBM BlueGene supercomputer and using the MilkyWay@HOME BOINC Internet computing project1. The asynchronous searches not only perform faster on heterogeneous grid environments as compared to synchronous search, but also achieve better convergence rates for the astronomy model used as the driving application, providing a strong argument for their use on grid computing environments and by the Milky Way@Home BOINC Internet computing project.

This paper describes initial research in addressing the challenges of managing quality of information for wireless sensor network target tracking with multiple missions of various priorities tracking multiple targets. We address the use of a distributed market-based mechanism to equalize the information value loss (that itself is a function of quality of information (QoI)) of tracked targets across multiple tracking missions while managing network congestion arising as a result of tracking. This includes considering missionspsila priorities and starvation of missionspsila data updates. In support of this approach, we define QoI as a function of the precision of position prediction of a tracked target and the loss of information value as the product of QoI and the priority of the mission tracking the target.

This article advocates a new computing paradigm, called computing with time, that is capable of efficiently performing a certain class of computation, namely, searching in parallel for the closest value to the given parameter. It shares some features with the idea of computing with action potentials proposed by Hopfield, which originated in the field of artificial neuron networks. The basic idea of computing with time is captured in a novel distributed algorithm based on broadcast communication called the lecture hall algorithm, which can compute the minimum among n positive numbers, each residing on a separate processor, using only O(1) broadcasts. When applied to sensor networks, the lecture hall algorithm leads to an interesting routing protocol having several desirable properties.

Malleability enables a parallel application's execution system to split or merge processes modifying granularity. While process migration is widely used to adapt applications to dynamic execution environments, it is limited by the granularity of the application's processes. Malleability empowers process migration by allowing the application's processes to expand or shrink following the availability of resources. We have implemented malleability as an extension to the PCM (process checkpointing and migration) library, a user-level library for iterative MPI applications. PCM is integrated with the Internet operating system (IOS), a framework for middleware-driven dynamic application reconfiguration. Our approach requires minimal code modifications and enables transparent middleware- triggered reconfiguration. Experimental results using a two-dimensional data parallel program that has a regular communication structure demonstrate the usefulness of malleability.

This paper presents GMLE1, a generic and distributed framework for maximum likelihood evaluation. GMLE is currently being applied to astroinformatics for determining the shape of star streams in the Milky Way galaxy, and to particle physics in a search for theory-predicted but yet unobserved sub-atomic particles. GMLE is designed to enable parallel and distributed executions on platforms ranging from supercomputers and high-performance homogeneous computing clusters to more heterogeneous Grid and Internet computing environments. GMLE's modular implementation seperates concerns of developers into the distributed evaluation frameworks, scientific models, and search methods, which interact through a simple API. This allows us to compare the benefits and drawbacks of different scientific models using different search methods on different computing environments. We describe and compare the performance of two implementations of the GMLE framework: an MPI version that more effectively uses homogeneous environments such as IBM's BlueGene, and a SALSA version that more easily accommodates heterogeneous environments such as the Rensselaer Grid. We have shown GMLE to scale well in terms of computation as well as communication over a wide range of environments. We expect that scientific computing frameworks, such as GMLE, will help bridge the gap between scientists needing to analyze ever larger amounts of data and ever more complex distributed computing environments.

We have designed a maximum likelihood fitter using the actor model to distribute the computation over a heterogeneous network. The prototype implementation uses the SALSA programming language and the Internet Operating System middleware. We have used our fitter to perform a partial wave analysis of particle physics data. Preliminary measurements have shown good performance and scalability. We expect our approach to be applicable to other scientific domains, such as biology and astronomy, where maximum likelihood evaluation is an important technique. We also expect our performance results to scale to Internet-wide runtime infrastructures, given the high adaptability of our software framework.

To address the problem of unsupervised outlier detection in wireless sensor networks, we develop an algorithm that (1) is flexible with respect to the outlier definition, (2) works in-network with a communication load proportional to the outcome, and (3) reveals its outcome to all sensors. We examine the algorithm’s performance using simulation with real sensor data streams. Our results demonstrate that the algorithm is accurate and imposes a reasonable communication load and level of power consumption.

This paper proposes a novel method of fusing models for classification of unbalanced data. The unbalanced data contains a majority of healthy (negative) instances, and a minority of unhealthy (positive) instances. The applicability of this type of classification problem with security applications inspired the naming of such problems as security classification problems (SCP). The area under the ROC curve (AUC) is the metric utilized to measure classifier performance, and in order to better understand AUC and ROC behavior, pseudo-ROC curves created from simulated data are introduced. ROC curves depend entirely upon the rankings created by classifiers. The rank distributions discussed in this paper display classifier performance in a novel form, and the behavior of these rank distributions provides insight into classifier fusion for the SCP. Rank distributions, which illustrate the probability of a particular rank containing a positive or negative instance, will be introduced and used to explain why synergistic classifier fusion occurs.

This paper explores a novel ensemble technique for unsupervised classification using nonparametric statistics. Multiple classification systems (MCS), or ensemble techniques, involve considering several classification methods or multiple outputs from the same method and devising techniques to reach a decision. The performance of a binary classification system can be measured on a receiver operating characteristic (ROC) curve, and the area under the curve (AUC) is exactly the Wilcoxon rank sum or Mann-Whitney U statistic, both of which are nonparametric statistics based upon ranked data. Successful performance of an unsupervised ensemble can be measured through the AUC, and the performance of different aggregation techniques for the combination of the multiple classification system decision values, or rankings in this paper, is illustrated. Aggregation techniques are based upon fuzzy logic theory, creating the fuzzy ROC curve. The one-class SVM is utilized for the unsupervised classification.

This paper studies pricing mechanisms for short-term contracts for network services in a recurring auction with sealed bids. We propose and evaluate a novel winner selection policy in such an auction. The new approach was motivated by an observation that in a recurring auction enough customers must be willing to participate in future auction rounds to prevent collapse of prices. Using simulations, we compare the proposed mechanism with traditional ones. The results demonstrate that the new method (i) increases revenues of the network service provider, (ii) minimizes loss of fairness, and (iii) enlarges the active customer base of a recurring auction.

The complexity of today's VLSI chip designs makes verification a necessary step before fabrication. As a result, gate-level logic simulation has became an integral component of the VLSI circuit design process which verifies the design and analyzes its behavior. Since the designs constantly grow in size and complexity, there is a need for ever more efficient simulations to keep the gate-level logic verification time acceptably small. The focus of this paper is an efficient simulation of large chip designs. We present the design and implementation of a new parallel simulator, called DSIM, and demonstrate DSIM's efficiency and speed by simulating a million gate circuit using different numbers of processors.

This paper presents self-selective routing, a self-maintained and fault-tolerant routing protocol for wireless ad hoc networks. The protocol combines broadcast radio transmissions with the novel autonomous programming technique, called self-selection, to support routing without the overhead of traditional ad hoc route maintenance. Moreover, the protocol routes packets through a dynamically established and nearly optimal path between two wireless nodes. In the paper, we present simulation results that demonstrate that self-selective routing is scalable and maintains highly sustained performance, even for heavy network traffic and under frequent network node and link faults.

We address the problem of detecting masquerading, a security attack in which an intruder assumes the identity of a legitimate user. Many approaches based on hidden Markov models and various forms of finite state automata have been proposed to solve this problem. The novelty of our approach results from the application of techniques used in bioinformatics for a pair-wise sequence alignment to compare the monitored session with past user behavior. Our algorithm uses a semiglobal alignment and a unique scoring system to measure similarity between a sequence of commands produced by a potential intruder and the user signature, which is a sequence of commands collected from a legitimate user. We tested this algorithm on the standard intrusion data collection set. As discussed, the results of the test showed that the described algorithm yields a promising combination of intrusion detection rate and false positive rate, when compared to published intrusion detection algorithms.

In most computer systems, page fault rate is currently minimized by generic page replacement algorithms which try to model the temporal locality inherent in programs. In this paper, we propose two algorithms, one greedy and the other stochastic, designed for program specific code restructuring as a means of increasing spatial locality within a program. Both algorithms e#ectively decrease average working set size and hence the page fault rate. Our methods are more e#ective than traditional approaches due to use of domain information. We illustrate the e#cacy of our algorithms on actual data mining algorithms.

We describe the use of machine learning for pattern recognition in magnetocardiography (MCG) that measures magnetic fields emitted by the electrophysiological activity of the heart. We used direct kernel methods to separate abnormal MCG heart patterns from normal ones. For unsupervised learning, we introduced Direct Kernel based Self-Organizing Maps. For supervised learning we used Direct Kernel Partial Least Squares and (Direct) Kernel Ridge Regression. These results are then compared with classical Support Vector Machines and Kernel Partial Least Squares. The hyperparameters for these methods were tuned on a validation subset of the training data before testing. We also investigated the most effective pre-processing, using local, vertical, horizontal and two-dimensional (global) Mahanalobis scaling, wavelet transforms and experimented with variable selection by filtering. The results, similar for all three methods, were encouraging, exceeding the quality of classification achieved by the trained experts.

The complexity and dynamics of the Internet is driving the demand for scalable and effective network control. This paper proposes a collaborative on-line simulation architecture to provide pro-active and automated control functions for networks. The general model includes autonomous on-line simulators which continuously monitor/model the network conditions and execute a search in the parameter state space for better settings of the protocol parameters. The protocol parameters are then tuned by the on-line simulation system. We describe the building blocks of this architecture and investigate the implementation challenges in the areas of network modeling, on-line simulation and parameter search. We also discuss the applicability of this system and present the simulation and test results of a preliminary implementation.

The paper describes an implementation of a large heterogeneous distributed parallel computation that counts the distribution of twin primes and calculates Brun's constant and maximal distances between pairs of twin primes. Two primes are twins if they differ by two. It is not known if there are infinitely many twin primes but it was proven that the sum of their inverses converges to the value defined as Brun's constant. Prior to this work, the number of twins and their contribution to Brun's constant was known for all twins up to 10/sup 14/. The authors have advanced this calculation to 2/spl middot/10/sup 15/ and are planning to continue to 10/sup 16/. The computation is distributed using the farmer-workers paradigm. The farmer divides the numerical range into intervals of 10 billion. Workers are assigned intervals to analyze and return results. If a worker fails, e.g., it does not return results within a given time period, the farmer reassigns its intervals to other workers. The farmer also frequently saves its state. If the farmer dies, a new one can be started up with minimal loss of work. The paper describes the algorithm for locating twin primes, a modified Sieve of Eratosthenes. It also discusses the method for distributing the work to clients, time and space saving optimizations, and multi-platform support. They conclude by presenting some preliminary results up to 1.8/spl middot/10/sup 15/ future directions for the system.

A new simple solution to the Lamport's concurrent programming problem is presented. The algorithm uses five distinct values of shared memory per process. The shared values can be stored either in a single variable or in three one-bit Boolean variables assigned to each process. The algorithm exhibits strong fairness property by enforcing the linear wait. It can be made immune to two types of errors typical to VLSI chip based multiprocessor systems: process failures and restarts, and read errors occurring during writes.

Concurrent systems are typically large and complex, requiring long, development time and much labor. They are, therefore, prime candidates for simplification and automation of the design and programming process. Their major application areas include real time systems, operating systems and cooperative computation. New applications are emerging with the trends towards wide usage of personal computers connected in a network and towards use of parallel processing in supercomputer architectures.

The use of an assertive specification language for real-time software development and maintenance is considered. The language is used for asserting the acts or relations inherent in the problem to be solved; this is in contrast to conventional programming languages, which are used to express the computer solution. Expressing a problem in Model consists of declaring array variables and defining their relationships through equations. This is different from conventional programming, which relates the problem in terms of computer operations. The language is supported by an automatic system which interacts with the user in soliciting missing definitions or correcting inconsistencies, and which translates the specification into a near-optimal computer solution. The main advantages of this approach are indicated. The use of Model in real-time software development and maintenance is reviewed. Differences from conventional programming are stressed through an example, which also illustrates the use of the three automatic components of the Model system.

An efficient algorithm for synchronized termination of iterative solution of simultaneous equations in a distributed message passing system is presented.The algorithm is based on an assumption that distributed processors are connected via unidirectional channels into a strongly connected network, in which no central controller exists.The number of processors and the network configuration are not known a priori.

An efficient decentralized algorithm for synchronized termination of a distributed computation is presented. It is assumed that distributed processes are connected via unidirectional channels into a strongly connected network, in which no central controller exists. The number of processes and the network configuration are not known a priori. The number of steps required to terminate distributed computation after all processes met their local termination conditions is proportional to the diameter D of the network (D + 1 steps).