Yubao Wu

Yubao Wu

Auto-generated profile, based on publicly available information

Yubao Wu

Georgia State University

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 February 2015 in Proceedings of the VLDB Endowment
Verified
Journal Article
Open access
YWYubao Wu
Yubao Wu
RJRuoming Jin
Ruoming Jin
JLJing Li
Jing Li
XZXiang Zhang
Xiang Zhang
Given a large network, local community detection aims at finding the community that contains a set of query nodes and also maximizes (minimizes) a goodness metric. This problem has recently drawn intense research interest. Various goodness metrics have been proposed. However, most existing metrics tend to include irrelevant subgraphs in the detected local community. We refer to such irrelevant subgraphs as free riders. We systematically study the existing goodness metrics and provide theoretical explanations on why they may cause the free rider effect. We further develop a query biased node weighting scheme to reduce the free rider effect. In particular, each node is weighted by its proximity to the query node. We define a query biased density metric to integrate the edge and node weights. The query biased densest subgraph, which has the largest query biased density, will shift to the neighborhood of the query nodes after node weighting. We then formulate the query biased densest connected subgraph (QDC) problem, study its complexity, and provide efficient algorithms to solve it. We perform extensive experiments on a variety of real and synthetic networks to evaluate the effectiveness and efficiency of the proposed methods.

11 August 2013
Verified
Conference Paper
Open access
WCWei Cheng
Wei Cheng
XZXiang Zhang
Xiang Zhang
ZGZhishan Guo
Zhishan Guo
YWYubao Wu
Yubao Wu
PSPatrick F. Sullivan
Patrick F. Sullivan
WWWei Wang
Wei Wang

18 June 2014
Verified
Conference Paper
Open access
YWYubao Wu
Yubao Wu
RJRuoming Jin
Ruoming Jin
XZXiang Zhang
Xiang Zhang
Given a large graph and a query node, finding its k-nearest-neighbor (kNN) is a fundamental problem. Various random walk based measures have been developed to measure the proximity (similarity) between nodes. Existing algorithms for the random walk based top-k proximity search can be categorized as global and local methods based on their search strategies. Global methods usually require an expensive precomputing step. By only searching the nodes near the query node, local methods have the potential to support more efficient query. However, most existing local search methods cannot guarantee the exactness of the solution. Moreover, they are usually designed for specific proximity measures. Can we devise an efficient local search method that applies to different measures and also guarantees result exactness? In this paper, we present FLoS (Fast Local Search), a unified local search method for efficient and exact top-k proximity query in large graphs. FLoS is based on the no local optimum property of proximity measures. We show that many measures have no local optimum. Utilizing this property, we introduce several simple operations on transition probabilities, which allow developing lower and upper bounds on the proximity. The bounds monotonically converge to the exact proximity when more nodes are visited. We further show that FLoS can also be applied to measures having local optimum by utilizing relationship among different measures. We perform comprehensive experiments to evaluate the efficiency and applicability of the proposed method.

1 April 2015
Verified
Conference Paper
Closed access
YWYubao Wu
Yubao Wu
RJRuoming Jin
Ruoming Jin
XZXiaofeng Zhu
Xiaofeng Zhu
XZXiang Zhang
Xiang Zhang
Finding dense subgraphs is an important problem that has recently attracted a lot of interests. Most of the existing work focuses on a single graph (or network 1 ). In many real-life applications, however, there exist dual networks, in which one network represents the physical world and another network represents the conceptual world. In this paper, we investigate the problem of finding the densest connected subgraph (DCS) which has the largest density in the conceptual network and is also connected in the physical network. Such pattern cannot be identified using the existing algorithms for a single network. We show that even though finding the densest subgraph in a single network is polynomial time solvable, the DCS problem is NP-hard. We develop a two-step approach to solve the DCS problem. In the first step, we effectively prune the dual networks while guarantee that the optimal solution is contained in the remaining networks. For the second step, we develop two efficient greedy methods based on different search strategies to find the DCS. Different variations of the DCS problem are also studied. We perform extensive experiments on a variety of real and synthetic dual networks to evaluate the effectiveness and efficiency of the developed methods.

1 September 2016 in Proceedings of the VLDB Endowment
Verified
Journal Article
Open access
PDF file
YWYubao Wu
Yubao Wu
YBYuchen Bian
Yuchen Bian
XZXiang Zhang
Xiang Zhang
Measuring the proximity between different nodes is a fundamental problem in graph analysis. Random walk based proximity measures have been shown to be effective and widely used. Most existing random walk measures are based on the first-order Markov model, i.e., they assume that the next step of the random surfer only depends on the current node. However, this assumption neither holds in many real-life applications nor captures the clustering structure in the graph. To address the limitation of the existing first-order measures, in this paper, we study the second-order random walk measures, which take the previously visited node into consideration. While the existing first-order measures are built on node-to-node transition probabilities, in the second-order random walk, we need to consider the edge-to-edge transition probabilities. Using incidence matrices, we develop simple and elegant matrix representations for the second-order proximity measures. A desirable property of the developed measures is that they degenerate to their original first-order forms when the effect of the previous step is zero. We further develop Monte Carlo methods to efficiently compute the second-order measures and provide theoretical performance guarantees. Experimental results show that in a variety of applications, the second-order measures can dramatically improve the performance compared to their first-order counterparts.

28 June 2019 in IEEE Transactions on Computational Social Systems
Verified
Journal Article
Closed access
WTWenyi Tang
Wenyi Tang
GLGuangchun Luo
Guangchun Luo
YWYubao Wu
Yubao Wu
LTLing Tian
Ling Tian
XZXu Zheng
Xu Zheng
ZCZhipeng Cai
Zhipeng Cai
In social networks, several influential individuals can promote an idea or a product to numerous individuals. Thus, it is valuable to solve the influence maximization (IM) problem, which asks for finding the most influential set of individuals in a social network. To estimate the influence of individuals, the existing independent cascade (IC) model simulates the influence diffusion only considering the influences from direct in-neighbors to nodes. This consideration does not hold in real life. In many cases, people are likely influenced by information depending on where it comes from, instead of who gives it. To simulate the influence diffusion more accurate, this paper proposes the second-order IC model, which takes the previous influence into consideration. In addition, we design an approximate algorithm and its distributed extension for IM under the second-order IC model. Experimental results show that our second-order IC model outperforms the IC model in terms of simulating influence diffusions. The proposed algorithms are efficient, and the obtained node sets are influential.