Search

Ranking nodes in uncertain graph is computationally expensive when the graph is huge due to the extremely large number of possible worlds. Some approximation is needed in general. We focus on PageRank centrality measure to rank and propose a method that does not use any approximation for uncertain graph in which all the links can be uncertain. We first compute the expected transition matrix over all the possible graphs accurately and then run PageRank algorithm only once to rank the nodes (p-avg approach). This is not the same as computing the scores for each individual graph first and then rank the nodes by taking their average (s-avg approach). Exact computation of the latter is not possible because of the heavy computational load and only the approximate scores are obtained by limiting the number of graphs by sampling. We have tested the performance from various angles using three real world networks. We show that the proposed method (p-avg approach) gives very high precision to the s-avg approach for highly ranked nodes and can be a good alternative to it. Pactically, the p-avg approach runs orders of magnitude, i.e., sample size, faster than the s-avg approach.

The problem of efficiently identifying critical nodes that substantially degrade network performance if they do not function is crucial and essential in analyzing a large complex network such as social networks on the Web, and it is still challenging. In this paper, we tackle this problem under a realistic situation where each link is probabilistically disconnected reflecting that an information path between two persons in a social network is not always open to pass on a message, rather than assuming that every information path is always open and passes on any information from one to the other. To solve this problem, we focus on the articulation point and utilize the bridge detection technique in graph theory to efficiently identify critical nodes in case the node reachability is taken as the performance measure. This corresponds to the total number of people who can receive information issued by every single person in a social network. Using two real-world social networks, we empirically show that the proposed method has a good scalability with respect to the network size and the nodes our method identified possesses unique properties and they are difficult to be identified by using conventional centrality measures.

Social Media allows people to post widely and share the posted online-items. Such items gain their popularity by the amount of attention received. Thus, studies on modeling the arrival process of attention to an individual item have recently attracted a great deal of interest. In this paper, we propose, by combining a Dirichlet process with a Hawkes process in a novel way, a probabilistic model, called cooperative Hawkes process (CHP) model, to discover the cooperative structure among all the items involved. The proposed model takes into account all the arrival processes of shares for those items. We develop an efficient method of inferring the CHP model from the observed sequences of share events, and present an effective framework for predicting the future popularity of each of these items. Using synthetic data and real data from a cooking-recipe sharing site, we demonstrate the effectiveness of the CHP model, and uncover the cooperative structure among cooking-recipes in view of attention dynamics.

Due to the increasing popularity of cooking-recipe sharing sites and the success of complex network science, attention has recently been devoted to developing an effective networkbased method of analyzing the characteristics of ingredient combinations used in recipes. Unlike previous approaches dealing with static properties, we aim at analyzing the dynamical changes in ingredient pairs jointly used in recipes, and propose an efficient method of extracting the change patterns for co-occurrence activities of ingredients. Based on the extracted change patterns, we build an active network among ingredients at every timestep, and identify active co-occurrence patterns. Moreover, we provide a method of interpreting active co-occurrence patterns in terms of recipes, and present a framework for visually analyzing their dynamical changes. Using real data from a Japanese recipe sharing site, we quantitatively demonstrate the effectiveness of the proposed method for extracting the activity change patterns for ingredient pairs, and uncover the characteristics of the seasonal changes in ingredient pairs jointly used in Japanese recipes by applying the proposed method.

Group centrality is an extension of the conventional node centrality in which the importance of a group of nodes together is the target for performance evaluation. We used this notion and formulated a link creation problem to a spatial network. The kind of problem we want to solve is to find the best places to construct k new roads to maximize the evacuation performance. The problem is formulated as an optimization problem to maximize the gain of the group closeness centrality by creating a set of new roads (k links) with the constraints on the road range distance (link length limit Δ). The problem is NP-hard. We show that this problem is reduced to a node selection problem and the objective function is submodular when there is no constraint on the link length limit. We devised an efficient greedy algorithm to search for the best k new roads under the constraint of Δ that comprises three steps: centrality calculation, parents selection and nodes selection. We applied this algorithm to three real road networks of different cities and evaluated its performance with respect to k and Δ. The algorithm is quite efficient and obtains the efficiency gain of 10^3 to 10^6 compared with a naive method in which every single node is blindly tested as a candidate from which to create a new road.

Acquiring a network of trust relations among users in social media sites, e.g., item-review sites, is important for analyzing users' behavior and efficiently finding reliable information on the Web. We address the problem of predicting trustlinks among users for an item-review site. Non-negative matrix factorization (NMF) methods have recently been shown useful for trust-link prediction in such a site where both link and activity information is available. Here, a user activity in an item-review site means posting a review and giving a rating for an item. In this paper, for better trust-link prediction, we propose a new NMF method that incorporates people's evaluation of users' activities as well as trust-links and users' activities themselves. We further apply it to an analysis of users' behavior. Using two real world item-review sites, we experimentally demonstrate the effectiveness of the proposed method.

In this paper, we investigate and compare the system-level throughput of non-orthogonal multiple access (NOMA) with a successive interference canceller (SIC) and orthogonal multiple access (OMA) in the downlink using a realistic file transfer protocol (FTP) traffic model. In the FTP traffic model, a user is assigned a finite payload to transmit when it arrives, and it leaves the system after the payload transmission is completed. This model is more realistic than the full-buffer traffic model, which is assumed in previous NOMA investigations. Furthermore, we evaluate the system-level throughput with various user scheduling criteria. Under the realistic finite-payload traffic model, a very high throughput gain in the vicinity of the cell using NOMA can be translated to improve the cell-edge user experience. Through extensive computer simulations, we clarify the behavior of NOMA with a SIC in the realistic traffic model in conjunction with various user scheduling criteria. The simulation results suggest that NOMA with a SIC is a promising multiple access scheme for systems beyond 4G.

Ultraviolet light-emitting diodes (UV-LEDs) have started replacing ultraviolet lamps. The power of UV-LEDs has greatly improved and the cost has decreased. In this paper, we attempt to understand the technologies and potential of UV-LEDs.

Node influence is yet another useful concept to quantify how important each node is over a network and can share the same role that other centrality measures have. It can provide new insight into the information diffusion phenomena such as existence of epidemic threshold which the other topology-based centralities cannot do. We focus on information diffusion process based on the SIR model, and address the problem of efficiently estimating the influence degree for all the nodes in the network. The proposed approach is a further improvement over the existing work of the bond percolation process [1], [2] which was demonstrated to be very effective, i.e., three orders of magnitude faster than direct Monte Carlo simulation, in approximately solving the influence maximization problem under a greedy search strategy. We introduce two pruning techniques which improve computational efficiency by an order of magnitude. This is a generic approach for the SIR model setting and can be instantiated to any specific diffusion model. It does not require any approximations or assumptions to the model, e.g., small diffusion probability, shortest path, maximum influence path, etc., that were needed in the existing approaches. We demonstrate its effectiveness by extensive experiments on two large real social networks. Main finding includes that different network structures have different epidemic thresholds and the node influence can identify influential nodes that the other centrality measures cannot.

The Island Model encourages genetic diversity, and often displays better search performance than single population models. In order to enhance the Island Model in the framework of genetic programming (GP), we propose a novel migration strategy based on frequent trees, where the frequent trees in an island mean the sub-trees appearing frequently among the individuals in the island. The proposed method evaluates each island by measuring its activation level in terms of not only how high the best fitness value is but also how many types of frequent trees are newly created, and then makes several individuals migrate from an island with high activation level to an island with low activation level, and vice versa. Using three benchmark problems widely adopted in the literature, we demonstrate that performance improvement can be achieved through incorporating the information of frequent trees into a migration strategy, and the proposed method significantly outperforms a typical method of the Island Model GP.

One of the most well studied issues in genetic programming is how to make building blocks efficiently. To make building blocks, it is important to find the substructures that appear in the individuals with higher fitness. Recently, a method based on frequent substructures has been proposed, and it has shown good performance; however, the depth of trees is not considered in the method. In this paper, we propose a hybrid crossover that involves the consideration of a combination of frequent trees and the depth of trees and apply the proposed method to symbolic regression problems. We experimentally demonstrate the effectiveness of the proposed method.

We address the problem of predicting missing links for a social network in Social Media by using user activity data. We propose a simple and natural probabilistic model with latent features (traits) for simultaneously generating links and activities in the set of nodes, and present an efficient method of learning the model from the observed links and activities. In order to estimate the total number of latent features and the probability distribution of them for each node from the observed data, we incorporate a hierarchical Dirichlet process (HDP) into the model. On the basis of the learned model, we present a method of predicting missing links in the social network. We experimentally show by using synthetic data that the proposed learning method can estimate the link creation probabilities in good accuracy when there is an enough amount of training data. Moreover, using real and synthetic data, we experimentally demonstrate the effectiveness of the proposed link prediction method.

We compare the electrical properties and interface characteristics in terms of nitrogen depth distribution and hydrogen diffusion behavior of two CVD oxide tunnel films that were nitrided by NO and N 2 O gas, respectively. The N 2 O-oxynitride shows a stronger resistance against the approach of the SiO 2 /Si interface by diffusing hydrogen in nuclear reaction analysis. This H diffusion behavior correlates with a characteristic N distribution in the tunnel oxide. The superior electrical quality of N 2 O-oxynitride over the NO-oxynitride is attributed to the existence of a N-rich H-diffusion barrier layer in the front of the oxynitride/Si interface.

In this paper, a method for extracting and classifying movement-related brain signals is proposed. A single-trial MEG observation is first processed with a pre-whitening filter so that strong stationary interference is eliminated. Next, a brain signal effective for classification is extracted using an adaptive spatial filter. The extracted signal is then classified with a support vector machine. From the experimental results, it is shown that the classification rate of 62.6 % is obtained for the brain signals related to the three types of hand movements (“scissors-paper-rock”).

We have proposed neural-network based visualization approach, called sequence-based SOM (self-organizing map) that visualizes transition of dynamic clusters by introducing the sequencing weight function onto the neuron topology. This approach mitigates the problems with a sliding window-based method. In this paper, we confirmed the properties of the proposed method via artificial data sets, and a real news articles data set by showing the topicspsila derivation and diversification/convergence. Visualization of cluster transition aids in the comprehension of such phenomena which come useful in various domains such as fault diagnosis and medical check-up, among others.

We consider the problem of finding influential nodes for information diffusion on a social network under the independent cascade model. It is known that the greedy algorithm can give a good approximate solution for the problem. Aiming to obtain efficient methods for finding better approximate solutions, we explore what structural feature of the underlying network is relevant to the greedy solution that is the approximate solution by the greedy algorithm. We focus on the SR-community structure, and analyze the greedy solution in terms of the SR-community structure. Using real large social networks, we experimentally demonstrate that the SR-community structure can be more strongly correlated with the greedy solution than the community structure introduced by Newman and Leicht.

In this paper, a generalized eigenvalue decomposition (GEVD)- based approach is proposed to remove continuous interferences included in MEG observations. The GEVD-based approach can be interpreted as a general framework of pre-whitening that can be combined with various types of signal separation techniques such as principal component analysis (PCA), independent component analysis (ICA) or adaptive beamforming (ABF). An example of extracting movement-related brain activities from single trial data is presented.

We propose an imaging system of brain surface and skull by considering the ultrasonic refraction of the skull. We do an experiment by using a cow scapula to imitate the skull bone and a biological phantom to imitate cerebral sulcus. We first visualize the shape of skull. We second calculate the thickness of the skull aided by fuzzy logic. Finally, we calculate the refractive angle of ultrasonic wave and visualize the image referring to the refraction of ultrasonic wave. In the result of applying this method, we can successfully visualize the phantom surface image.

We propose a new unsupervised learning method called multinomial PCA (MuPCA) for efficiently extracting the major latent topics from a document stream based on the "bag-of-words" (BOW) representation of a document. Unlike PCA, MuPCA follows a suitable probabilistic generative model for the document stream represented as time-series of word-frequency vectors. Using real data of document streams on the Web, we experimentally demonstrate the effectiveness of the proposed method.

We propose a growing network model and its learning algorithm. Unlike the conventional scale-free models, we incorporate community structure, which is an important characteristic of many real-world networks including the Web. In our experiments, we confirmed that the proposed model exhibits a degree distribution with a power-law tail, and our method can precisely estimate the probability of a new link creation from data without community information. Moreover, by introducing a measure of dynamic hub-degrees, we could predict the change of hub-degrees between communities.

It is necessary to know how quickly and how accurately humans can react when sensory stimulations are presented around them in order to construct a virtual reality system. We have been studying how quickly and accurately subjects can indicate targets such as a bursting sound and a flashing light presented around them without seeing their arm. The motion induced by the sensory stimulation is called "sensory-motor co-ordination". In this report, the angle error between the indicated angle and the target angle was measured as a function of the target angle (Case 1). This result was compared with the angle error between the indicated angle and the angle informed by an operator using spoken words (Case 2). In the experimental setup, the 19 LEDs and speakers were arranged inside a hemi-spaced cylinder and the distance from the subject to the targets was 0.5 m. The duration of the presented targets was 0.2 sec. The indicated angles were detected by a touch panel attached to the hemispaced cylinder. The subjects were asked not to move their head or eyes during the experiment. From the experimental results, the degree of error increased in the peripheral area, and the error in case 1 was smaller than in case 2. We discussed the reason for this and the design of virtual reality systems. >

A biasing scheme for sensing circuits, namely an automated bias control (ABC) circuit, for high-performance VLSIs is described. The ABC circuit can automatically gear the output level of sensing circuits to the input threshold voltage of the succeeding CMOS converters. The sensing performance can be accelerated with the ABC circuit either by reducing the excessive signal level margin between the sensing circuits and the CMOS converters or by reducing extra stages of signal amplification. Since feedback control of the ABC circuit ensures correct DC biasing even under large process deviations and circuit condition changes, a wider operation margin can also be obtained. Three successful applications of the ABC circuit are reported: a sense amplifier, an address transition detector (ATD), and an ECL-CMOS input buffer. A 64-kb BiCMOS SRAM employing the proposed sense amplifier and the ATD has been fabricated with a 0.8- mu m 9-GHz BiCMOS technology. The SRAM has an address access time of 4.5 ns. >