We challenge the problem of efficiently identifying critical links that substantially degrade network performance if they do not function under a realistic situation where each link is probabilistically disconnected, e.g., unexpected traffic accident in a road network and unexpected server down in a communication network. To solve this problem, we utilize the bridge detection technique in graph theory and efficiently identify critical links in case the node reachability is taken as the performance measure.To be more precise, we define a set of target nodes and a new measure associated with it, Target-oriented latent link Criticalness Centrality (TCC), which is defined as the marginal loss of the expected number of nodes in the network that can reach, or equivalently can be reached from, one of the target nodes, and compute TCC for each link by use of detected bridges. We apply the proposed method to two real-world networks, one from social network and the other from spatial network, and empirically show that the proposed method has a good scalability with respect to the network size and the links our method identified possess unique properties. They are substantially more critical than those obtained by the others, and no known measures can replace the TCC measure.

We address the problem of opening and closing shops in group competitive environment, i.e., shops in the same group work cooperatively and those in different groups competitively, and analyze how the market share and location changes over time. We formulate a stochastic utility of each shop as a function of shop distance and attractiveness from which a market share is computed by weighting consumers buying power. We further place a constraint on the traveling time, which is crucial to reduce the computation time, and use a marginal gain of the market share as a measure to rank the candidate location. Using the real dataset of three convenience stores in four cities in Japan, we confirm that, despite the simplification we made in the model, rankings of the existing shops are shown to be high which implies that our model is reasonable. Further, comparison with the baseline gravity model shows that our model gives much more realistic results. Analyses of the dynamics of opening and closing shops indicate that the reasonable time-bound for walking is about 10 min., the market share of each group, thus total share, eventually increases although small, and the difference of the share within each group gradually becomes smaller, revealing that the spatial distribution of the shops in each group becomes more uniform.

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.

At its heart the act of reviewing is very subjective, but in reality many factors would influence user’s decision. This can be called social influence bias. We pick two factors, “Who” and “When” and discuss which factor is more influential when a user posts his/her own rate in an online review syst em. We consider two kinds of users: real and virtual. In the former each user has its own metric, but in the latter the metric is assigned to the order of review posting actions (rating). We propose a weighted multinomial generative model that can learn the factor metric quite efficiently from a vast amount of data already available in many online review systems. If the model can explain the data well enough, this implies that such a social bias does exist. We evaluate the proposed method and confirm its effectiveness by five review datasets, and empirically clarify that there is no universal solution, but the social bias does exist. In reality the influential factor depends on each dataset, the majority of users is normal (average), and there are two small groups of users, each with high metric value and low metric value.

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.

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.

We address a problem of efficiently estimating the influence of a node in information diffusion over a social network. Since the information diffusion is a stochastic process, the influence degree of a node is quantified by the expectation, which is usually obtained by very time consuming many runs of simulation. Our contribution is that we proposed a framework for predictive simulation based on the leave-N-out cross validation technique that well approximates the error from the unknown ground truth for two target problems: one to estimate the influence degree of each node, and the other to identify top-K influential nodes. The method we proposed for the first problem estimates the approximation error of the influence degree of each node, and the method for the second problem estimates the precision of the derived top-K nodes, both without knowing the true influence degree. We experimentally evaluate the proposed methods using the three real world networks, and show that they can serve as a good measure to solve the target problems with far fewer runs of simulation ensuring the accuracy if N is appropriately chosen, and that estimating the top-K nodes is easier than estimating the influence degree, which means one can identify the influential nodes without knowing exactly their influence degree.

We address a problem of detecting changes in information posted to social media taking both content and posting time distributions into account. To this end, we introduce a generative model consisting of two components, one for a content distribution and the other for a timing distribution, approximating the shape of the parameter change by a series of step functions. We then propose an efficient algorithm to detect change points by maximizing the likelihood of generating the observed sequence data, which has time complexity almost proportional to the length of observed sequence (possible change points). We experimentally evaluate the method on synthetic data streams and demonstrate the importance of considering both distributions to improve the accuracy. We, further, apply our method to real scoring stream data extracted from a Japanese word-of-mouth communication site for cosmetics and show that it can detect change points and the detected parameter change patterns are interpretable through an in-depth investigation of actual reviews.

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.

We addressed the problem of detecting the change in behavior of information diffusion over a social network which is caused by an unknown external situation change using a small amount of observation data in a retrospective setting. The unknown change is assumed effectively reflected in changes in the parameter values in the probabilistic information diffusion model, and the problem is reduced to detecting where in time and how long this change persisted and how big this change is. We solved this problem by searching the change pattern that maximizes the likelihood of generating the observed information diffusion sequences, and in doing so we devised a very efficient general iterative search algorithm using the derivative of the likelihood which avoids parameter value optimization during each search step. This is in contrast to the naive learning algorithm in that it has to iteratively update the patten boundaries, each requiring the parameter value optimization and thus is very inefficient. We tested this algorithm for two instances of the probabilistic information diffusion model which has different characteristics. One is of information push style and the other is of information pull style. We chose Asynchronous Independent Cascade (AsIC) model as the former and Value-weighted Voter (VwV) model as the latter. The AsIC is the model for general information diffusion with binary states and the parameter to detect its change is diffusion probability and the VwV is the model for opinion formation with multiple states and the parameter to detect its change is opinion value. The results tested on these two models using four real-world network structures confirm that the algorithm is robust enough and can efficiently identify the correct change pattern of the parameter values. Comparison with the naive method that finds the best combination of change boundaries by an exhaustive search through a set of randomly selected boundary candidates shows that the proposed algorithm far outperforms the native method both in terms of accuracy and computation time.

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.

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 estimating the parameters, from observed data in a complex social network, for an information diffusion model that takes time-delay into account, based on the popular independent cascade (IC) model. For this purpose we formu

We address the problem of predicting the expected opinion share over a social network at a target time from the opinion diffusion data under the value-weighted voter model with multiple opinions. The value update algorithm ensures that it converges to a correct solution and the share prediction results outperform a simple linear extrapolation approximation when the available data is limited. We further show in an extreme case of complete network that the opinion with the highest value eventually takes over, and the expected share prediction problem with uniform opinion value is not well-defined and any opinion can win.

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 (ldquoscissors-paper-rockrdquo).

We address the problem of minimizing the propagation of undesirable things, such as computer viruses or malicious rumors, by blocking a limited number of links in a network, which is converse to the influence maximization problem in which the most influential nodes for information diffusion is searched in a social network. This minimization problem is more fundamental than the problem of preventing the spread of contamination by removing nodes in a network. We introduce two definitions for the contamination degree of a network, accordingly define two contamination minimization problems, and propose methods for efficiently finding good approximate solutions to these problems on the basis of a naturally greedy strategy. Using large social networks, we experimentally demonstrate that the proposed methods outperform conventional link-removal methods. We also show that unlike the case of blocking a limited number of nodes, the strategy of removing nodes with high out-degrees is not necessarily effective for these problems.

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 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 structual 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.

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.

This article extends previous mathematical studies on elucidating the redundancy for describing functions by feedforward neural networks (FNNs) to the elucidation of redundancy for describing dynamical systems (DSs) by continuous-time recurrent neural networks (RNNs). In order to approximate a DS on R(n) using an RNN with n visible units, an n-dimensional affine neural dynamical system (A-NDS) can be used as the DS actually produced by the above RNN under an affine map from its visible state-space R(n) to its hidden state-space. Therefore, we consider the problem of clarifying the redundancy for describing A-NDSs by RNNs and affine maps. We clarify to what extent a pair of an RNN and an affine map is uniquely determined by its corresponding A-NDS and also give a nonredundant sufficient search set for the DS approximation problem based on A-NDS.

An approach is presented for building a 3-D world model from range image sequences derived from road scenes including moving objects. First, a range image is transformed into a height map representing the height information from the assumed ground plane, and then it is segmented into the ground plane and objects on it. In order to capture the resolution and accuracy of the range information and to represent the consistency of the height information between different height maps, the authors define a reliability of the height information for each point on the height map. Using the reliability, the system finds the correspondences of both static and moving objects between different observations, and successively refines the height information and its reliability with newly acquired data, dealing with inconsistent data. The authors show the results obtained using landscape models and a range finder based on the structured light. >