NS Seminar: Paper Presentations

Date and Location

Oct 03, 2016 - 2:00pm to 3:00pm
Network Science Lab, Bldg 434, Room 122


Haleigh Wright, CS Trainee
Yi Ding, CS Trainee


Scalability and Egalitarianism in Peer-to-Peer Networks

Fabio Caccioli, Giacomo Livan and Tomaso Aste

Many information-technology innovations are driven, in their early stages, by an egalitarian ethos that empowers individuals through dis-intermediation. Bitcoin and peer to peer financial systems were inspired by these egalitarian ambitions. However, in bitcoin we have recently witnessed a strong centralization around a few large mining pools, which puts control of most of the system in the hands of a few. In this chapter we investigate the physical limits of distributed consensus mechanisms over networks, and discuss whether there are scalability and efficiency reasons that incentivize centralization. We compute the time to reach majority consensus in a variety of settings, comparing egalitarian networks with centralized networks, and quantifying the effect of network topology on the propagation of information.


Large-Scale Object Classification using Label Relation Graphs

Jia Dengy, Nan Ding, Yangqing Jia, Andrea Frome, Kevin Murphy, Samy Bengio, Yuan Li, Hartmut Neven, Hartwig Adam

In this paper we study how to perform object classification in a principled way that exploits the rich structure of real world labels. We develop a new model that allows encoding of exible relations between labels. We introduce Hierarchy and Exclusion (HEX) graphs, a new formalism that captures semantic relations between any two labels applied to the same object: mutual exclusion, overlap and subsumption. We then provide rigorous theoretical analysis that illustrates properties of HEX graphs such as consistency, equivalence, and computational implications of the graph structure. Next, we propose a probabilistic classication
fimodel based on HEX graphs and show that it enjoys a number of desirable properties. Finally, we evaluate our method using a large-scale benchmark. Empirical results demonstrate that our model can significantly improve object classication by exploiting the label relations.