Clustering Link Data - Theory and Algortithms

人类活动的许多领域都以有向图为特征：社交网络中的互动、引用网络、像网络这样的超链接领域、公司之间的贸易关系、航空旅行的模式。聚类是在这种局部相互作用的网络中发现全局结构的一种通用技术。目前，对于具有非对称关系的网络，通常采用适用于无向图的方法对其进行对称再聚类。提出了一种针对有向网络聚类的理论框架和算法。我将使用我开发的随机漫步视图（random walksview）来完成这个任务，该视图已被证明在无向图的聚类方面是成功的。

Many domains of human activity are characterized by directed graphs:interactions in social networks, citation networks, hyperlinkeddomains like the web, trade relations between companies, patterns ofair travel. Clustering is a general technique to discover globalstructure in such networks of local interactions. Presently, networkswith asymmetric relations are first symmetrized then clustered bymethods applicable to undirected graphs. This proposal shows thatsymmetrization often loses the information about structure and proposeto develop a theoretical framework and algorithms for clustering ofdirected networks. I will approach the task using the random walksview that I developed and which has proved successful at clustering inundirected graphs.