九州大学 伊都キャンパス
ウェスト2号館3階 第5・6講義室（W2-325室）

November 16 (Mon)
13:30-14:30 Nicolas Rivera (King's College London, UK),
The Linear Voting Model

Abstract:
 We study a general model of probabilistic voting on graphs called the 
Linear Voting Model. The model is flexible enough to include some 
well-known models as pull voting and push voting. Under certain 
conditions the linear voting model has several desirable properties, 
in particular it reaches consensus and the consensus time is finite. 
By the use of analytic techniques we investigate problems such as the 
probability that a certain opinion wins the polling, the influence of 
high/low degree vertices and the time to reach consensus.


14:50-15:50 Colin Cooper (King's College London, UK),
Vacant sets and vacant nets: Critical times
for simple and modified random walks

Abstract:
  The first part of the talk is an introduction to the idea of the 
vacant set of a discrete random walk. The vacant set of a random walk 
is the set of  vertices of the graph not visited by the walk. 
Similarly, the vacant net is the set of unvisited edges.

  We study the change in size and  structure of the graph induced by 
the vacant set as the walk proceeds.  A critical time is a step of 
the walk before which the graph of the vacant set contains large 
unexplored connected components, and after which it contains only 
small unexplored components. For some classes of random graphs we can 
find a precise critical time.

  In the second part of the talk, we compare the critical time on 
these graphs for three types of random walks (simple, non-
backtracking, unexplored edges first). In order to  break the graph 
up into small unexplored components as quickly as possible, the walk 
with the earliest critical time is best.


問合せ：来嶋（B01）