Search

We provide a framework for analyzing geographical influence networks that have impacts on visit event sequences for a set of point-of-interests (POIs) in a city. Since mutually-exciting Hawkes processes can naturally model temporal event data and capture interactions between those events, previous work presented a probabilistic model based on Hawkes processes, called CHP model, for finding cooperative structure among online items from their share event sequences. In this paper, based on Hawkes processes, we propose a novel probabilistic model, called RH model, for detecting geographical competitive structure in the set of POIs, and present a method of inferring it from the POI visit event history. We mathematically derive an analytical approximation formula for predicting the popularity of each of the POIs for the RH model, and also extend the CHP model so as to extract geographical cooperative structure. Using synthetic data, we first confirm the effectiveness of the inference method and the validity of the approximation formula. Using real data of Location-Based Social Networks (LBSNs), we demonstrate the significance of the RH model in terms of predicting the future events, and uncover the latent geographical influence networks from the perspective of geographical competitive and cooperative structures.

We focus on a class of link injection problem of spatial network, i.e., finding best places to construct k new roads that save as many people as possible in a time-critical emergency situation. We quantify the network performance by node coverage under the presence of time constraint and propose an efficient algorithm that maximizes the marginal gain by use of lazy evaluation making the best of time constraint. We apply our algorithm to three problem scenarios (disaster evacuation, ambulance call, fire engine dispatch) using real-world road network and geographical information of actual facilities and demonstrate that 1) use of lazy evaluation can achieve nearly two orders of magnitude reduction of computation time compared with the straightforward approach and 2) the location of new roads is intuitively explainable and reasonable.

We address the problem of modeling the occurrence process of events for visiting attractive places, called points-of-interest (POIs), in a sightseeing city in the setting of a continuous time-axis and a continuous spatial domain, which is referred to as modeling geographical attention dynamics. By combining a Hawkes process with a time-varying Gaussian mixture model in a novel way and incorporating the influence structure depending on time slots as well, we propose a probabilistic model for discovering the spatio-temporal influence structure among major sightseeing areas from the viewpoint of geographical attention dynamics, and aim to accurately predict POI visit events in the near future. We develop an efficient method of inferring the parameters in the proposed model from the observed sequence of POI visit events, and present an analysis method for the geographical attention dynamics. Using real data of POI visit events in a Japanese sightseeing city, we demonstrate that the proposed model outperforms conventional models in terms of predictive accuracy, and uncover the spatio-temporal influence structure among major sightseeing areas in the city from the perspective of geographical attention dynamics.

We address a problem of efficiently estimating value of a centrality measure for a node in a large network, and propose a sampling-based framework in which only a small number of nodes that are randomly selected are used to estimate the measure. The error estimator we derived is an unbiased estimator of the approximation error defined as the expectation of the difference between the true and the estimated values of the centrality. We experimentally evaluate the fundamental performance of the proposed framework using the closeness and betweenness centralities on six real world networks from different domains, and show that it allows us to estimate the approximation error more tightly and more precisely than the standard error estimator traditionally used based on i.i.d. sampling, i.e., with the confidence level of \(95\%\) for a small number of sampling, say \(20\%\) of the total number of nodes.

In this paper, we focus on an emergency situation in the real-world such as disaster evacuation and propose an algorithm that can efficiently identify critical links in a spatial network that substantially degrade network performance if they fail to function. For that purpose, we quantify the network performance by node reachability from/to one of target facilities within the prespecified time limitation, which corresponds to the number of people who can safely evacuate in a disaster. Using a real-world road network and geographical information of actual facilities, we demonstrated that the proposed method is much more efficient than the method based on the betweenness centrality that is one of the representative centrality measures and that the critical links detected by our method cannot be identified by using a straightforward extension of the betweenness centrality.

We address the problem of efficiently detecting critical links in a large network in order to maintain network performance, e.g., in case of disaster evacuation, for which a probabilistic link disconnection model plays an essential role. Here, critical links are such links that their disconnection exerts substantial effects on the network performance such as the average node reachability. We tackle this problem by proposing a new method consisting of two new acceleration techniques: reachability condition skipping (RCS) and distance constraints skipping (DCS). We tested the effectiveness of the proposed method by using three real-world spatial networks. In particular, we show that the proposed method achieves the efficiency gain of around \(10^4\) compared with a naive method in which every single link is blindly tested as a critical link candidate.

Efficiently identifying critical links that substantially degrade network performance if they fail to function is challenging for a large complex network. In this paper, we tackle this problem under a more realistic situation where each link is probabilistically disconnected as if a road is blocked in a natural disaster than assuming that any road is never blocked in a disaster. 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, which corresponds to the number of people who can reach at least one evacuation facility in a disaster. Using two real-world road networks, we empirically show that the proposed method is much more efficient than the other methods that are based on traditional centrality measures and the links our method detected are substantially more critical than those by the others.

We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance such as the average node reachability. We tackle this problem by proposing a new method which consists of one existing and two new acceleration techniques: redundant-link skipping (RLS), marginal-node pruning (MNP) and burn-out following (BOF). All of them are designed to avoid unnecessary computation and work both in combination and in isolation. We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks. In particular, we showed that the new method can compute the performance degradation by link removal without introducing any approximation within a comparable computation time needed by the bottom-k sketch which is a summary of dataset and can efficiently process approximate queries, i.e., reachable nodes, on the original dataset, i.e., the given network.

We address the problem of modeling trust network evolution through social communications among users in a social media site. In particular, we focus on a social trust-link created between two users having mediating-objects such as mediating-users and mediating-items, and analyze the time-decay effects of mediating-objects on social trust-link creation. To this end, we first introduce the basic TCM model that can be regarded as a conventional link prediction method based on mediating-objects, and propose the TCM model with time-decay by incorporating an appropriate time-decay function into it. We present an efficient learning method of the proposed model, and apply it to an analysis of social trust-link creation for two real item-review sites. We show that the proposed model significantly outperforms the basic TCM model in terms of prediction performance, and clarify several properties of user behavior for social trust-link creation.

In this paper, by focusing on spatial networks embedded in the real space, we first extend the conventional step-based closeness and betweenness centralities by incorporating inter-nodes link distances obtained from the positions of nodes. Then, we propose a method for accelerating computation of these centrality measures by pruning some nodes and links based on the cut links of a given spatial network. In our experiments using spatial networks constructed from urban streets of cities of several types, our proposed method achieved about twice the computational efficiency compared with the baseline method. Actual amount of reduction in computation time depends on network structures. We further experimentally show by examining the highly ranked nodes that the closeness and betweenness centralities have completely different characteristics to each other.

We address the problem of efficiently detecting critical links in a large network. Critical links are such links that their deletion exerts substantial effects on the network performance. Here in this paper, we define the performance as being the average node reachability. This problem is computationally very expensive because the number of links is an order of magnitude larger even for a sparse network. We tackle this problem by using bottom-k sketch algorithm and further by employing two new acceleration techniques: marginal-link updating (MLU) and redundant-link skipping (RLS). We tested the effectiveness of the proposed method using two real-world large networks and two synthetic large networks and showed that the new method can compute the performance degradation by link removal about an order of magnitude faster than the baseline method in which bottom-k sketch algorithm is applied directly. Further, we confirmed that the measures easily composed by well known existing centralities, e.g. in/out-degree, betweenness, PageRank, authority/hub, are not able to detect critical links. Those links detected by these measures do not reduce the average reachability at all, i.e. not critical at all.

We propose a simple and efficient method that learns and assesses the conformity of each user of an online review system from the observed review score record. The model we use is a modified Voter model that takes account of the conformity of each user. Conformity is learnable quite efficiently with a few tens of iterations by maximizing the log-likelihood given the observed data. The proposed method was evaluated and confirmed effective by two review datasets. It could identify both high and low conformity users. Users with high conformity are not necessarily early adopters. Their scores are influential to drive the consensus score. The user ranking of conformity was compared with Page Rank and HITS in which user network was roughly approximated by the directed graph induced by the observed data. The proposed method gives more interpretable ranking, and the global property of high conformity users was identified.

We address a problem of identifying nodes having a high centrality value in a large social network based on its approximation derived only from nodes sampled from the network. More specifically, we detect gaps between nodes with a given confidence level, assuming that we can say a gap exists between two adjacent nodes ordered in descending order of approximations of true centrality values if it can divide the ordered list of nodes into two groups so that any node in one group has a higher centrality value than any one in another group with a given confidence level. To this end, we incorporate confidence intervals of true centrality values, and apply the resampling-based framework to estimate the intervals as accurately as possible. Furthermore, we devise an algorithm that can efficiently detect gaps by making only two passes through the nodes, and empirically show, using three real world social networks, that the proposed method can successfully detect more gaps, compared to the one adopting a standard error estimation framework, using the same node coverage ratio, and that the resulting gaps enable us to correctly identify a set of nodes having a high centrality value.

We propose a method of detecting the points at which the speed of information diffusion changed from an observed diffusion sequence data over a social network, explicitly taking the network structure into account. Thus, change in diffusion is both spatial and temporal. This is different from most of the existing change detection approaches in which all the diffusion information is projected on a single time line and the search is made in this time axis. We formulate this as a search problem of change points and their respective change rates under the framework of maximum log-likelihood embedded in MDL. Time complexity of the search is almost proportional to the number of observed data points and the method is very efficient. We tested this using both a real Twitter date (ground truth not known) and the synthetic data (ground truth known), and demonstrated that the proposed method can detect the change points efficiently and the results are very different from the existing sequence-based (time axis) approach (Kleinberg’s method).

We propose a new item-ranking method that is reliable and can efficiently identify high-quality items from among a set of items in a given category using their review-scores which were rated and posted by users. Typical ranking methods rely only on either the number of reviews or the average review score. Some of them discount outdated ratings by using a temporal-decay function to make a fair comparison between old and new items. The proposed method reflects trust levels by incorporating a trust discount factor into a temporal-decay function. We first define the MTDF (Multinomial with Trust Discount Factor) model for the review-score distribution of each item built from the observed review data. We then bring in the notion of z-score to accommodate the trust variance that comes from the number of reviews available, and propose a z-score version of MTDF model. Finally we demonstrate the effectiveness of the proposed method using the MovieLens dataset, showing that the proposed ranking method can derive more reasonable and trustable rankings, compared to two naive ranking methods and the pure z-score based ranking method.

We address a problem of efficiently estimating value of a centrality measure for a node in a large social network only using a partial network generated by sampling nodes from the entire network. To this end, we propose a resampling-based framework to estimate the approximation error defined as the difference between the true and the estimated values of the centrality. We experimentally evaluate the fundamental performance of the proposed framework using the closeness and betweenness centralities on three real world networks, and show that it allows us to estimate the approximation error more tightly and more precisely with the confidence level of 95% even for a small partial network compared with the standard error traditionally used, and that we could potentially identify top nodes and possibly rank them in a given centrality measure with high confidence level only from a small partial network.

The word of mouth information over certain review sites affects various activities from person to person. In large-scale review sites, it can happen that evaluation tendency of a product changes in a large way by only a few reviews that were rated and posted by certain users. Thus, it is very important to be able to detect those influential reviews in social media analysis. We propose an algorithm that can efficiently divide stream data of review scores by maximizing the likelihood of generating the observed sequence data. We assume that the user’s fundamental scoring behavior follows a multinomial distribution model and formulate a division problem.

We analyze evolution of trust networks in social media sites from a perspective of mediators. To this end, we propose two stochastic models that simulate the dynamics of creating a trust link under the presence of mediators, the A-ME and A-MAE models, where the A-ME model analyzes mediator effects for trust-network evolution in terms of mediator types, and the A-MAE model, an extension of the A-ME model, analyzes mediator-activity effects for trust-network evolution. We present an efficient method of inferring the values of model parameters from an observed sequence of trust links and user activities. Using real data from Epinions, we experimentally show that the A-MAE model significantly outperforms the A-ME model for predicting trust links in the near future under the presence of mediators, and demonstrate the effectiveness of mediator-activity information for trust-network evolution. We further clarify, by using the A-ME and A-MAE models, several characteristic properties of trust-link creation probability in the Epinions data.