justin

Today I read a paper titled “Cops and Invisible Robbers: the Cost of Drunkenness”

The abstract is:
We examine a version of the Cops and Robber (CR) game in which the robber is invisible, i.e., the cops do not know his location until they capture him.

Apparently this game (CiR) has received little attention in the CR literature.

We examine two variants: in the first the robber is adversarial (he actively tries to avoid capture); in the second he is drunk (he performs a random walk).

Our goal in this paper is to study the invisible Cost of Drunkenness (iCOD), which is defined as the ratio ct_i(G)/dct_i(G), with ct_i(G) and dct_i(G) being the expected capture times in the adversarial and drunk CiR variants, respectively.

We show that these capture times are well defined, using game theory for the adversarial case and partially observable Markov decision processes (POMDP) for the drunk case.

We give exact asymptotic values of iCOD for several special graph families such as $d$-regular trees, give some bounds for grids, and provide general upper and lower bounds for general classes of graphs.

We also give an infinite family of graphs showing that iCOD can be arbitrarily close to any value in [2,infinty).

Finally, we briefly examine one more CiR variant, in which the robber is invisible and “infinitely fast”; we argue that this variant is significantly different from the Graph Search game, despite several similarities between the two games.

Today I read a paper titled “Opinion fluctuations and disagreement in social networks”

The abstract is:
We study a tractable opinion dynamics model that generates long-run disagreements and persistent opinion fluctuations.

Our model involves an inhomogeneous stochastic gossip process of continuous opinion dynamics in a society consisting of two types of agents: regular agents, who update their beliefs according to information that they receive from their social neighbors; and stubborn agents, who never update their opinions.

When the society contains stubborn agents with different opinions, the belief dynamics never lead to a consensus (among the regular agents).

Instead, beliefs in the society fail to converge almost surely, the belief profile keeps on fluctuating in an ergodic fashion, and it converges in law to a non-degenerate random vector.

The structure of the network and the location of the stubborn agents within it shape the opinion dynamics.

The expected belief vector evolves according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain with absorbing states corresponding to the stubborn agents and converges to a harmonic vector, with every regular agent’s value being the weighted average of its neighbors’ values, and boundary conditions corresponding to the stubborn agents’.

Expected cross-products of the agents’ beliefs allow for a similar characterization in terms of coupled Markov chains on the network.

We prove that, in large-scale societies which are highly fluid, meaning that the product of the mixing time of the Markov chain on the graph describing the social network and the relative size of the linkages to stubborn agents vanishes as the population size grows large, a condition of \emph{homogeneous influence} emerges, whereby the stationary beliefs’ marginal distributions of most of the regular agents have approximately equal first and second moments.

Today I read a paper titled “Egomunities, Exploring Socially Cohesive Person-based Communities”

The abstract is:
In the last few years, there has been a great interest in detecting overlapping communities in complex networks, which is understood as dense groups of nodes featuring a low outbound density.

To date, most methods used to compute such communities stem from the field of disjoint community detection by either extending the concept of modularity to an overlapping context or by attempting to decompose the whole set of nodes into several possibly overlapping subsets.

In this report we take an orthogonal approach by introducing a metric, the cohesion, rooted in sociological considerations.

The cohesion quantifies the community-ness of one given set of nodes, based on the notions of triangles – triplets of connected nodes – and weak ties, instead of the classical view using only edge density.

A set of nodes has a high cohesion if it features a high density of triangles and intersects few triangles with the rest of the network.

As such, we introduce a numerical characterization of communities: sets of nodes featuring a high cohesion.

We then present a new approach to the problem of overlapping communities by introducing the concept of ego-munities, which are subjective communities centered around a given node, specifically inside its neighborhood.

We build upon the cohesion to construct a heuristic algorithm which outputs a node’s ego-munities by attempting to maximize their cohesion.

We illustrate the pertinence of our method with a detailed description of one person’s ego-munities among Facebook friends.

We finally conclude by describing promising applications of ego-munities such as information inference and interest recommendations, and present a possible extension to cohesion in the case of weighted networks.

Today I read a paper titled “Effect of Embedding Watermark on Compression of the Digital Images”

The abstract is:
Image Compression plays a very important role in image processing especially when we are to send the image on the internet.

The threat to the information on the internet increases and image is no exception.

Generally the image is sent on the internet as the compressed image to optimally use the bandwidth of the network.

But as we are on the network, at any intermediate level the image can be changed intentionally or unintentionally.

To make sure that the correct image is being delivered at the other end we embed the water mark to the image.

The watermarked image is then compressed and sent on the network.

When the image is decompressed at the other end we can extract the watermark and make sure that the image is the same that was sent by the other end.

Though watermarking the image increases the size of the uncompressed image but that has to done to achieve the high degree of robustness i.e.

how an image sustains the attacks on it.

The present paper is an attempt to make transmission of the images secure from the intermediate attacks by applying the generally used compression transforms.

Today I read a paper titled “Can virtual reality predict body part discomfort and performance of people in realistic world for assembling tasks?”

The abstract is:
This paper presents our work on relationship of evaluation results between virtual environment (VE) and realistic environment (RE) for assembling tasks.

Evaluation results consist of subjective results (BPD and RPE) and objective results (posture and physical performance).

Same tasks were performed with same experimental configurations and evaluation results were measured in RE and VE respectively.

Then these evaluation results were compared.

Slight difference of posture between VE and RE was found but not great difference of effect on people according to conventional ergonomics posture assessment method.

Correlation of BPD and performance results between VE and RE are found by linear regression method.

Moreover, results of BPD, physical performance, and RPE in VE are higher than that in RE with significant difference.

Furthermore, these results indicates that subjects feel more discomfort and fatigue in VE than RE because of additional effort required in VE.

Today I read a paper titled “Signed Networks in Social Media”

The abstract is:
Relations between users on social media sites often reflect a mixture of positive (friendly) and negative (antagonistic) interactions.

In contrast to the bulk of research on social networks that has focused almost exclusively on positive interpretations of links between people, we study how the interplay between positive and negative relationships affects the structure of on-line social networks.

We connect our analyses to theories of signed networks from social psychology.

We find that the classical theory of structural balance tends to capture certain common patterns of interaction, but that it is also at odds with some of the fundamental phenomena we observe — particularly related to the evolving, directed nature of these on-line networks.

We then develop an alternate theory of status that better explains the observed edge signs and provides insights into the underlying social mechanisms.

Our work provides one of the first large-scale evaluations of theories of signed networks using on-line datasets, as well as providing a perspective for reasoning about social media sites.

Today I read a paper titled “A Decomposition Approach to Multi-Vehicle Cooperative Control”

The abstract is:
We present methods that generate cooperative strategies for multi-vehicle control problems using a decomposition approach.

By introducing a set of tasks to be completed by the team of vehicles and a task execution method for each vehicle, we decomposed the problem into a combinatorial component and a continuous component.

The continuous component of the problem is captured by task execution, and the combinatorial component is captured by task assignment.

In this paper, we present a solver for task assignment that generates near-optimal assignments quickly and can be used in real-time applications.

To motivate our methods, we apply them to an adversarial game between two teams of vehicles.

One team is governed by simple rules and the other by our algorithms.

In our study of this game we found phase transitions, showing that the task assignment problem is most difficult to solve when the capabilities of the adversaries are comparable.

Finally, we implement our algorithms in a multi-level architecture with a variable replanning rate at each level to provide feedback on a dynamically changing and uncertain environment.

Today I read a paper titled “Motion Planning via Manifold Samples”

The abstract is:
We present a general and modular algorithmic framework for path planning of robots.

Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with practical, considerably simpler sampling-based approaches that are appropriate for higher dimensions.

In order to facilitate the transfer of advanced geometric algorithms into practical use, we suggest taking samples that are entire low-dimensional manifolds of the configuration space that capture the connectivity of the configuration space much better than isolated point samples.

Geometric algorithms for analysis of low-dimensional manifolds then provide powerful primitive operations.

The modular design of the framework enables independent optimization of each modular component.

Indeed, we have developed, implemented and optimized a primitive operation for complete and exact combinatorial analysis of a certain set of manifolds, using arrangements of curves of rational functions and concepts of generic programming.

This in turn enabled us to implement our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles.

We demonstrate that the integration of several carefully engineered components leads to significant speedup over the popular PRM sampling-based algorithm, which represents the more simplistic approach that is prevalent in practice.

We foresee possible extensions of our framework to solving high-dimensional problems beyond motion planning.

Today I read a paper titled “Generalized Stable Matching in Bipartite Networks”

The abstract is:
In this paper we study the generalized version of weighted matching in bipartite networks.

Consider a weighted matching in a bipartite network in which the nodes derive value from the split of the matching edge assigned to them if they are matched.

The value a node derives from the split depends both on the split as well as the partner the node is matched to.

We assume that the value of a split to the node is continuous and strictly increasing in the part of the split assigned to the node.

A stable weighted matching is a matching and splits on the edges in the matching such that no two adjacent nodes in the network can split the edge between them so that both of them can derive a higher value than in the matching.

We extend the weighted matching problem to this general case and study the existence of a stable weighted matching.

We also present an algorithm that converges to a stable weighted matching.

The algorithm generalizes the Hungarian algorithm for bipartite matching.

Faster algorithms can be made when there is more structure on the value functions.

Today I read a paper titled “Crowdsourcing for Usability Testing”

The abstract is:
While usability evaluation is critical to designing usable websites, traditional usability testing can be both expensive and time consuming.

The advent of crowdsourcing platforms such as Amazon Mechanical Turk and CrowdFlower offer an intriguing new avenue for performing remote usability testing with potentially many users, quick turn-around, and significant cost savings.

To investigate the potential of such crowdsourced usability testing, we conducted two similar (though not completely parallel) usability studies which evaluated a graduate school’s website: one via a traditional usability lab setting, and the other using crowdsourcing.

While we find crowdsourcing exhibits some notable limitations in comparison to the traditional lab environment, its applicability and value for usability testing is clearly evidenced.

We discuss both methodological differences for crowdsourced usability testing, as well as empirical contrasts to results from more traditional, face-to-face usability testing.

Today I read a paper titled “A Vehicle for Research: Using Street Sweepers to Explore the Landscape of Environmental Community Action”

The abstract is:
Researchers are developing mobile sensing platforms to facilitate public awareness of environmental conditions.

However, turning such awareness into practical community action and political change requires more than just collecting and presenting data.

To inform research on mobile environmental sensing, we conducted design fieldwork with government, private, and public interest stakeholders.

In parallel, we built an environmental air quality sensing system and deployed it on street sweeping vehicles in a major U.S.

city; this served as a “research vehicle” by grounding our interviews and affording us status as environmental action researchers.

In this paper, we present a qualitative analysis of the landscape of environmental action, focusing on insights that will help researchers frame meaningful technological interventions.

Today I read a paper titled “Upper Tag Ontology (UTO) For Integrating Social Tagging Data”

The abstract is:
Data integration and mediation have become central concerns of information technology over the past few decades.

With the advent of the Web and the rapid increases in the amount of data and the number of Web documents and users, researchers have focused on enhancing the interoperability of data through the development of metadata schemes.

Other researchers have looked to the wealth of metadata generated by bookmarking sites on the Social Web.

While several existing ontologies capitalize on the semantics of metadata created by tagging activities, the Upper Tag Ontology (UTO) emphasizes the structure of tagging activities to facilitate modeling of tagging data and the integration of data from different bookmarking sites as well as the alignment of tagging ontologies.

UTO is described and its utility in harvesting, modeling, integrating, searching and analyzing data is demonstrated with metadata harvested from three major social tagging systems (Delicious, Flickr and YouTube).

Today I read a paper titled “Social Network Based Search for Experts”

The abstract is:
Our system illustrates how information retrieved from social networks can be used for suggesting experts for specific tasks.

The system is designed to facilitate the task of finding the appropriate person(s) for a job, as a conference committee member, an advisor, etc.

This short description will demonstrate how the system works in the context of the HCIR2012 published tasks.

Today I read a paper titled “Uncovering space-independent communities in spatial networks”

The abstract is:
Many complex systems are organized in the form of a network embedded in space.

Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks.

The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people’s movements and thus reveal their trajectories and spatial behaviour.

Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks.

In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology.

In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks.

We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes.

Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.

Today I read a paper titled “On Sharing Viral Video over an Ad Hoc Wireless Network”

The abstract is:
We consider the problem of broadcasting a viral video (a large file) over an ad hoc wireless network (e.g., students in a campus).

Many smartphones are GPS enabled, and equipped with peer-to-peer (ad hoc) transmission mode, allowing them to wirelessly exchange files over short distances rather than use the carrier’s WAN.

The demand for the file however is transmitted through the social network (e.g., a YouTube link posted on Facebook).

To address this coupled-network problem (demand on the social network; bandwidth on the wireless network) where the two networks have different topologies, we propose a file dissemination algorithm.

In our scheme, users query their social network to find geographically nearby friends that have the desired file, and utilize the underlying ad hoc network to route the data via multi-hop transmissions.

We show that for many popular models for social networks, the file dissemination time scales sublinearly with n; the number of users, compared to the linear scaling required if each user who wants the file must download it from the carrier’s WAN.

Today I read a paper titled “Automated Training and Maintenance through Kinect”

The abstract is:
In this paper, we have worked on reducing burden on mechanic involving complex automobile maintenance activities that are performed in centralised workshops.

We have presented a system prototype that combines Augmented Reality with Kinect.

With the use of Kinect, very high quality sensors are available at considerably low costs, thus reducing overall expenditure for system design.

The system can be operated either in Speech mode or in Gesture mode.

The system can be controlled by various audio commands if user opts for Speech mode.

The same controlling can also be done by using a set of Gestures in Gesture mode.

Gesture recognition is the task performed by Kinect system.

This system, bundled with RGB and Depth camera, processes the skeletal data by keeping track of 20 different body joints.

Recognizing Gestures is done by verifying user movements and checking them against predefined condition.

Augmented Reality module captures real-time image data streams from high resolution camera.

This module then generates 3D model that is superimposed on real time data.

Today I read a paper titled “BiopSym: a simulator for enhanced learning of ultrasound-guided prostate biopsy”

The abstract is:
This paper describes a simulator of ultrasound-guided prostate biopsies for cancer diagnosis.

When performing biopsy series, the clinician has to move the ultrasound probe and to mentally integrate the real-time bi-dimensional images into a three-dimensional (3D) representation of the anatomical environment.

Such a 3D representation is necessary to sample regularly the prostate in order to maximize the probability of detecting a cancer if any.

To make the training of young physicians easier and faster we developed a simulator that combines images computed from three-dimensional ultrasound recorded data to haptic feedback.

The paper presents the first version of this simulator.