Source author record

Tiancheng Lou

Tiancheng Lou appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Artificial Intelligence Computational Complexity Data Structures and Algorithms Networking and Internet Architecture physics.soc-ph Social and Information Networks

Catalog footprint

What is connected

4works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2015arXiv

Inferring Social Status and Rich Club Effects in Enterprise Communication Networks

Social status, defined as the relative rank or position that an individual holds in a social hierarchy, is known to be among the most important motivating forces in social behaviors. In this paper, we consider the notion of status from the perspective of a position or title held by a person in an enterprise. We study the intersection of social status and social networks in an enterprise. We study whether enterprise communication logs can help reveal how social interactions and individual status manifest themselves in social networks. To that end, we use two enterprise datasets with three communication channels --- voice call, short message, and email --- to demonstrate the social-behavioral differences among individuals with different status. We have several interesting findings and based on these findings we also develop a model to predict social status. On the individual level, high-status individuals are more likely to be spanned as structural holes by linking to people in parts of the enterprise networks that are otherwise not well connected to one another. On the community level, the principle of homophily, social balance and clique theory generally indicate a "rich club" maintained by high-status individuals, in the sense that this community is much more connected, balanced and dense. Our model can predict social status of individuals with 93% accuracy.

preprint2014arXiv

Optimal Rendezvous Strategies for Different Environments in Cognitive Radio Networks

In Cognitive Radio Networks (CRNs), the secondary users (SUs) are allowed to access the licensed channels opportunistically. A fundamental and essential operation for SUs is to establish communication through choosing a common channel at the same time slot, which is referred to as rendezvous problem. In this paper, we study strategies to achieve fast rendezvous for two secondary users. The channel availability for secondary nodes is subject to temporal and spatial variation. Moreover, in a distributed system, one user is oblivious of the other user's channel status. Therefore, a fast rendezvous is not trivial. Recently, a number of rendezvous strategies have been proposed for different system settings, but rarely have they taken the temporal variation of the channels into account. In this work, we first derive a time-adaptive strategy with optimal expected time-to-rendezvous (TTR) for synchronous systems in stable environments, where channel availability is assumed to be static over time. Next, in dynamic environments, which better represent temporally dynamic channel availability in CRNs, we first derive optimal strategies for two special cases, and then prove that our strategy is still asymptotically optimal in general dynamic cases. Numerous simulations are conducted to demonstrate the performance of our strategies, and validate the theoretical analysis. The impacts of different parameters on the TTR are also investigated, such as the number of channels, the channel open possibilities, the extent of the environment being dynamic, and the existence of an intruder.

preprint2013arXiv

On the Complexity of Connectivity in Cognitive Radio Networks Through Spectrum Assignment

Cognitive Radio Networks (CRNs) are considered as a promising solution to the spectrum shortage problem in wireless communication. In this paper, we initiate the first systematic study on the algorithmic complexity of the connectivity problem in CRNs through spectrum assignments. We model the network of secondary users (SUs) as a potential graph, where two nodes having an edge between them are connected as long as they choose a common available channel. In the general case, where the potential graph is arbitrary and the SUs may have different number of antennae, we prove that it is NP-complete to determine whether the network is connectable even if there are only two channels. For the special case where the number of channels is constant and all the SUs have the same number of antennae, which is more than one but less than the number of channels, the problem is also NP-complete. For the special cases in which the potential graph is complete, a tree, or a graph with bounded treewidth, we prove the problem is NP-complete and fixed-parameter tractable (FPT) when parameterized by the number of channels. Exact algorithms are also derived to determine the connectability of a given cognitive radio network.

preprint2011arXiv

Width-parameterized SAT: Time-Space Tradeoffs

Width parameterizations of SAT, such as tree-width and path-width, enable the study of computationally more tractable and practical SAT instances. We give two simple algorithms. One that runs simultaneously in time-space $(O^*(2^{2tw(ϕ)}), O^*(2^{tw(ϕ)}))$ and another that runs in time-space $(O^*(3^{tw(ϕ)\log{|ϕ|}}),|ϕ|^{O(1)})$, where $tw(ϕ)$ is the tree-width of a formula $ϕ$ with $|ϕ|$ many clauses and variables. This partially answers the question of Alekhnovitch and Razborov, who also gave algorithms exponential both in time and space, and asked whether the space can be made smaller. We conjecture that every algorithm for this problem that runs in time $2^{tw(ϕ)\mathbf{o(\log{|ϕ|})}}$ necessarily blows up the space to exponential in $tw(ϕ)$. We introduce a novel way to combine the two simple algorithms that allows us to trade \emph{constant} factors in the exponents between running time and space. Our technique gives rise to a family of algorithms controlled by two parameters. By fixing one parameter we obtain an algorithm that runs in time-space $(O^*(3^{1.441(1-ε)tw(ϕ)\log{|ϕ|}}), O^*(2^{2εtw(ϕ)}))$, for every $0<ε<1$. We systematically study the limitations of this technique, and show that these algorithmic results are the best achievable using this technique. We also study further the computational complexity of width parameterizations of SAT. We prove non-sparsification lower bounds for formulas of path-width $ω(\log|ϕ|)$, and a separation between the complexity of path-width and tree-width parametrized SAT modulo plausible complexity assumptions.