BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Liang-Hao Huang

Liang-Hao Huang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsSocial and Information NetworksData Structures and Algorithmsmath.CONetworking and Internet ArchitectureComputational Complexity

Catalog footprint

What is connected

6works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2016arXiv

Multicast Traffic Engineering for Software-Defined Networks

Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design an approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

When Social Influence Meets Item Inference

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of social influence and item inference (for product recommendation). We develop a new model, Social Item Graph (SIG), that captures both effects in form of hyperedges. Accordingly, we formulate a seed selection problem, called Social Item Maximization Problem (SIMP), and prove the hardness of SIMP. We design an efficient algorithm with performance guarantee, called Hyperedge-Aware Greedy (HAG), for SIMP and develop a new index structure, called SIG-index, to accelerate the computation of diffusion process in HAG. Moreover, to construct realistic SIG models for SIMP, we develop a statistical inference based framework to learn the weights of hyperedges from data. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental result validates our ideas and demonstrates the effectiveness and efficiency of the proposed model and algorithms over baselines.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scalable Steiner Tree for Multicast Communications in Software-Defined Networking

Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, but at the same time the scalability problem becomes more serious since traffic is more difficult to be aggregated. Those crucial issues in SDN have been studied for unicast but have not been explored for multicast traffic, and addressing those issues for multicast is more challenging since the identities and the number of members in a multicast group can be arbitrary. In this paper, therefore, we propose a new multicast tree for SDN, named Branch-aware Steiner Tree (BST). The BST problem is difficult since it needs to jointly minimize the numbers of the edges and the branch nodes in a tree, and we prove that it is NP-Hard and inapproximable within $k$, which denotes the number of group members. We further design an approximation algorithm, called Branch Aware Edge Reduction Algorithm (BAERA), to solve the problem. Simulation results demonstrate that the trees obtained by BAERA are more bandwidth-efficient and scalable than the shortest-path trees and traditional Steiner trees. Most importantly, BAERA is computation-efficient to be deployed in SDN since it can generate a tree on massive networks in small time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Target set selection problem for honeycomb networks

Let $G$ be a graph with a threshold function $θ:V(G)\rightarrow \mathbb{N}$ such that $1\leq θ(v)\leq d_G(v)$ for every vertex $v$ of $G$, where $d_G(v)$ is the degree of $v$ in $G$. Suppose we are given a target set $S\subseteq V(G)$. The paper considers the following repetitive process on $G$. At time step 0 the vertices of $S$ are colored black and the other vertices are colored white. After that, at each time step $t>0$, the colors of white vertices (if any) are updated according to the following rule. All white vertices $v$ that have at least $θ(v)$ black neighbors at the time step $t-1$ are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Finding a target set $S$ of smallest possible size such that all vertices in $G$ are black at the end of the process. Such an $S$ is called an {\em optimal target set} for $G$ under the threshold function $θ$. We are interested in finding an optimal target set for the well-known class of honeycomb networks under an important threshold function called {\em strict majority threshold}, where $θ(v)=\lceil (d_G(v)+1)/2\rceil$ for each vertex $v$ in $G$. In a graph $G$, a {\em feedback vertex set} is a subset $S\subseteq V(G)$ such that the subgraph induced by $V(G)\setminus S$ is cycle-free. In this paper we give exact value on the size of the optimal target set for various kinds of honeycomb networks under strict majority threshold, and as a by-product we also provide a minimum feedback vertex set for different kinds regular graphs in the class of honeycomb networks

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Some Results on the Target Set Selection Problem

In this paper we consider a fundamental problem in the area of viral marketing, called T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if $G$ is a block-cactus graph, then the T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem can be solved in linear time, which generalizes Chen's result \cite{chen2009} for trees, and the time complexity is much better than the algorithm in \cite{treewidth} (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph $G$ is a chordal graph with thresholds $θ(v)\leq 2$ for each vertex $v$ in $G$, then the problem can be solved in linear time. For a Hamming graph $G$ having thresholds $θ(v)=2$ for each vertex $v$ of $G$, we precisely determine an optimal target set $S$ for $(G,θ)$. These results partially answer an open problem raised by Dreyer and Roberts \cite{Dreyer2009}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Target Set Selection Problem on Cycle Permutation Graphs, Generalized Petersen Graphs and Torus Cordalis

In this paper we consider a fundamental problem in the area of viral marketing, called T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem. In a a viral marketing setting, social networks are modeled by graphs with potential customers of a new product as vertices and friend relationships as edges, where each vertex $v$ is assigned a threshold value $θ(v)$. The thresholds represent the different latent tendencies of customers (vertices) to buy the new product when their friend (neighbors) do. Consider a repetitive process on social network $(G,θ)$ where each vertex $v$ is associated with two states, active and inactive, which indicate whether $v$ is persuaded into buying the new product. Suppose we are given a target set $S\subseteq V(G)$. Initially, all vertices in $G$ are inactive. At time step 0, we choose all vertices in $S$ to become active. Then, at every time step $t>0$, all vertices that were active in time step $t-1$ remain active, and we activate any vertex $v$ if at least $θ(v)$ of its neighbors were active at time step $t-1$. The activation process terminates when no more vertices can get activated. We are interested in the following optimization problem, called T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION}: Finding a target set $S$ of smallest possible size that activates all vertices of $G$. There is an important and well-studied threshold called strict majority threshold, where for every vertex $v$ in $G$ we have $θ(v)=\lceil{(d(v) +1)/2}\rceil$ and $d(v)$ is the degree of $v$ in $G$. In this paper, we consider the T{\scriptsize ARGET} S{\scriptsize ET} S{\scriptsize ELECTION} problem under strict majority thresholds and focus on three popular regular network structures: cycle permutation graphs, generalized Petersen graphs and torus cordalis.

0 citations0 reviewsNo code linkedOpen access