Research
1. Information/technology diffusion over networksks
The diffusion of information or technology innovation is highly affected how people get new information and exchange new ideas or behaviors. A user will adopt new information/ behavior/technology only when he gets benefit from it. Users’ decision making depends not only on the benefit of the information/technology but also on the number of users who choose the given information/technology. For example, if there are more users choosing Windows OS than Mac OS, then it might be better to use Window OS because Windows OS gives more convenience such as compatibility or many applications than Mac OS. Such influence is called “network externality”. In this research, I proposed two models in which a user will adopt a new technology only if the choice of new technology gives her higher utility, which depends on the number of existing users who already adopted the new technology. Using these models, I characterized when an entrant technology (new information) is pervasively adopted than an incumbent technology and examined the resulting dynamics.
As an extension of my prior work, I worked on information diffusion over social networks, which investigated how the global information affects the information diffusion speed when rational individuals are located on a given network with an arbitrary graph structure. I have proved that global information impedes the diffusion of information when users make a strategic choice.
I also studied how diffusion effect can be maximized by seeding a subset of individuals (within a given budget), i.e., convincing them to pre-adopt a new innovation. In this work, polynomial-time approximation algorithms were proposed for three representative graphs classes, Erdos–Rényi graphs (representing well-connected graphs), planted partition graphs (representing locally well connected graphs with big clusters) and geometrically structured graphs (representing locally well connected with small clusters), respectively. First, it is shown that for the dense Erdos–Rényi graphs and planted partition graphs, an arbitrary seeding and a simple seeding proportional to the size of clusters are almost optimal with high probability. Second, for geometrically structured sparse graphs, it is shown that the proposed algorithm that (a) constructs clusters, (b) seeds the border individuals among clusters, and (c) greedily seeds inside each cluster always outputs an almost optimal solution.
The list of my work on this research topic is provided below.
- Modeling and analysis of technology/information diffusion over a complete network and the role of converters.
- Modeling and analysis of technology/information diffusion over a complete network with bounded rational users using aspiration-based learning.
- The impact of global information on information/technology diffusion over general networks.
- Influence maximization over social networks
- Worm propagation modeling.
2. A channel aware MAC protocol in an Aloha network with selfish users
An intrinsic characteristic of wireless channel is time varying due to mobility and interference. In time varying environment, users have diverse channel conditions. Some users have better channel conditions than some other users. If users are cooperative to follow prescribed protocols, such diverse channel conditions (called multiuser diversity) can be exploited to increase total throughput for distributed random access protocols. In this work, I showed that total throughput can be increased by using multiuser diversity even in the presence of selfish users who maximize their own benefit. In general myopic selfish user decisions cause deterioration of system-wide performance. Hence it is doubtful whether the total throughput increases when selfish behaviors exist. I proposed a distributed channel aware random access protocol for selfish users and showed that multiuser diversity can be exploited to enhance total throughput despite selfish user behaviors. The result contrasts with another one that the total throughput of the standard Aloha (i.e. using no channel information) with selfish users is decreasing due to competition as the number of users is increasing.
3. Peer-to-peer systems
It is very well known that pervasive free-riding deteriorates the performance of content distribution in p2p networks. Regarding to the free-riding, I worked on
- Analyzing the impact of selfish behaviors on content distribution in hybrid p2p networks consisting of a single server and many peers and
- Developing an incentive mechanism for content-sharing in a fully distributed p2p network.
In the former work, I analyzed how the server load changes in a p2p network when a fraction of peers is selfish. I mathematically proved that the server load is bounded as the number of peers is increasing when a fraction of peers refuse to share contents. This result implies that a hybrid p2p network does not mandate an incentive mechanism for the scalability of content- sharing, which is quite surprising since it is commonly believed an incentive mechanism for content-sharing is essential for the scalability of a p2p network.
In the latter work, I modeled a simple deterministic stratified epidemic model of the dissemination of a single popular file by peer-to-peer networks that employ Bit-Torrent like incentives. Using the model, I evaluated the effectiveness of such incentives by comparison with a system that does not segment files and always involves only a single file transfer per transaction.
4. Economics of Wi-Fi offloading
Wi-Fi offloading, where users use Wi-Fi instead of 3G at the cost of delay when they have delay-tolerant data to send/receive, has been proposed a cost-effective and practical solution to save significant cellular capacity. I analyzed the benefit of Wi-Fi offloading for a market consisting of a network service provider and users. It is shown that Wi-Fi offloading is beneficial to both the provider and the users since the provider’s revenue and the users’ surplus (defined by utility – cost) are increased, when Wi-Fi offloading is employed.
5. MAC, distributed access rate control protocols and pricing for selfish users
As the Internet has evolved into a vast heterogeneous system, comprised of independent and selfish users who value the benefits they derive from the network much more than the efficiency of the network as a whole, the need for new reliable distributed resource allocation methods considering selfish users has emerged. Taking into account that selfish users may modify the current standard congestion protocols and exploit other users’ cooperation, I have abandoned the paradigm of assumed-cooperative users in the networks and considered networks with all selfish users who pursue only their own benefits. I modeled the heterogeneous and non-cooperative user behaviors as non-cooperative games and developed distributed user access rate control algorithms for selfish users in wireless and wired networks. Users can make their own decisions to maximize their benefit from the networks and do not care about other users’ interests. I have worked on applying prices and other incentives to modeling, congestion control, and optimization of resource distribution in distributed networks of selfish and non-cooperative users.
In such non-cooperative distributed networks, one of the biggest questions is whether the network will work stable or experience congestion collapse. To prevent network collapse, I considered disincentives to the excessive use of network resources, for example, usage-based pricing. I found conditions that guarantee stable equilibrium points of the proposed non-cooperative resource allocation methods in various networks.
The specific research activities on this topic are:
- Random access protocols with altruism.
- An adaptive contention window control in wireless LANs(IEEE 802.11).
- QoS aware resource allocation in differentiated services.
- Adaptive distributed rate control for non-cooperative users in circuit switched networks under fixed usage pricing.
- A transmission rate control in TCP-like networks.
- A transmission rate control algorithm and pricing strategy in Aloha networks.