Exploiting The Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
Exploiting The Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
复制标题
DOI：
10.1080/15427951.2014.958250
复制
发表时间：
2014-11
影响因子：
--
通讯作者：
Jérôme Kunegis
中科院分区：
文献类型：
--
作者：
Jérôme Kunegis
摘要本文将几种代数图分析方法推广到二部网络。在科学、工程和商业的各个领域，许多类型的信息都可以表示为网络，因此，网络分析学科在这些领域中发挥着重要作用。一类强大而广泛的网络分析方法是基于代数图论的，即，将图表示为正方形邻接矩阵。然而，许多网络都有一种非常特殊的形式，与这种代表性相冲突：它们是双向的。也就是说，它们由两种节点类型组成，每条边连接一种类型的节点和另一种类型的节点。二分网络（也称为双模式网络）的示例包括个人及其所属的社会群体、音乐艺术家及其演奏的音乐流派以及文本文档及其包含的词语。事实上，任何类型的特征都可以用分类变量表示，可以解释为二分网络。虽然二分网络很普遍，但网络分析领域的大多数文献都集中在单分网络上，即，这些网络只有一种类型的节点。本文的目的是将一些重要的代数网络分析方法扩展到二分网络，表明代数图论中的许多方法都可以应用于二分网络，只需稍加修改。我们展示了聚类，可视化和链接预测的方法。此外，我们引入了新的代数方法来衡量的双parativity近二部图。
Abstract In this article, we extend several algebraic graph analysis methods to bipartite networks. In various areas of science, engineering, and commerce, many types of information can be represented as networks, and thus, the discipline of network analysis plays an important role in these domains. A powerful and widespread class of network analysis methods is based on algebraic graph theory, i.e., representing graphs as square adjacency matrices. However, many networks are of a very specific form that clashes with that representation: they are bipartite. That is, they consist of two node types, with each edge connecting a node of one type with a node of the other type. Examples of bipartite networks (also called two-mode networks) are persons and the social groups they belong to, musical artists and the musical genres they play, and text documents and the words they contain. In fact, any type of feature that can be represented by a categorical variable can be interpreted as a bipartite network. Although bipartite networks are widespread, most literature in the area of network analysis focuses on unipartite networks, i.e., those networks with only a single type of node. The purpose of this article is to extend a selection of important algebraic network analysis methods to bipartite networks, showing that many methods from algebraic graph theory can be applied to bipartite networks, with only minor modifications. We show methods for clustering, visualization, and link prediction. Additionally, we introduce new algebraic methods for measuring the bipartivity in near-bipartite graphs.