A New Hypernetwork Model Based on Matrix
Operation
Shengjiu Liu
School of Information Science and Technology
Southwest Jiaotong University
Chengdu, China
liushengjiu2008@163.com
Tianrui Li
School of Information Science and Technology
Southwest Jiaotong University
Chengdu, China
trli@swjtu.edu.cn
Abstract—In this paper, we propose a new hypernetwork
model based on Tracy-Singh Product on the correlation matrix of
hypergraph. Node degree, node hyperdegree, and hyperedge
degree and their corresponding polynomials are introduced to
describe this hypernetwork model. It is shown that this kind of
hypernetworks is fractal as its correlation matrix is a fractal
matrix. The fractal parameter is then given. What’s more, this
kind of hypernetworks is also small-world for the diameter won’t
exceed twice the diameter of primitive hypergraph. By a novel
product of node degree polynomial, node hyperdegree
polynomial and hyperedge degree polynomial, node degree, node
hyperdegree and hyperedge degree are obtained.
Keywords—hypernetwork; matrix; fractal; small-world; node
degree; node hyperdegree; hyperedge degree
I. INTRODUCTION
Complex networks are models of graphs which show able to
capture the phenomenology of a plethora of systems, from
biology to the World Wide Web [1, 2]. Erdos and Renyi in
1959 defined the random network model, where an edge
between each pair of nodes is present with a probability [3].
Barabasi-Albert showed a new model of a complex network
which is based on a growth process and a preferential
attachment mechanism [4]. Watts and Strogatz presented the
small-world network which can be created by randomly
adding bonds to a regular 1D ring and then building a
superposition between regular lattices and classical random
graphs [5]. Based on generating functions in [6], Newman,
Strogatz and Watts [7] developed the theory of random graphs
with arbitrary degree distributions and derived exact
expressions for the position of the phase transition.
In a graph a link only relates a pair of nodes, but the edges
of the hypergraph, namley hyper-edges, can relate groups of
more than two nodes [8, 9]. Estrada and Rodriguez-Velazquez
introduced a new centrality measure that characterizes the
participation of each node in all subgraphs in a network [10].
Then they extended the concepts of subgraph centrality and
clustering for complex networks represented by hypergraphs:
complex hyper-networks [11]. Furthermore, they coined the
term complex hyper-networks to designate such systems
where nodes are grouped together in multi-dyadic
relationships represented by hyper-edges. Hu et al. built a new
evolving hypernetwork model and presented some basic
topological properties, e.g., node degrees, node hyperdegrees,
and hyperedge degrees [12]. Presently, hypernetworks have
received much attention. Many hypernetworks in the real
world have been presented and studied, like scientific
collaboration hypernetworks, actor collaboration
hypernetworks, World Wide Web and citation hypernetworks
[13, 14, 15, 16]. Hypernetwork can be described by either
correlation matrix or adjacency matrix [17]. Correlation
matrix is employed in this study since it is Boole and one
correlation matrix maps to one and only one hypernetwork.
In this paper, we construct a new hypernetwork model
based on Tracy-Singh Product on correlation matrix of a
primitive hypergraph by an iterative approach. It is fractal
since its correlation matrix is a fractal matrix. We also give its
fractal parameter. In addition, it is small-world because its
diameter won’t exceed twice the diameter of primitive
hypergraph. Finally, we obtain its node degree, node
hyperdegree, and hyperedge degree by a novel product of
node degree polynomial, node hyperdegree polynomial and
hyperedge degree polynomial.
The rest of this paper is organized as follows. In Section Ċ,
hypergraph, matrix operation and fractal theory are reviewed.
In Section ċ, a new hypernetwork model is presented together
with its properties. In Section Č, several examples of the
hypernetwork model are provided. The paper ends with
conclusions and further research topics in Section č.
II. PRELIMINARIES
A. Hypergraph
A hypergraph is a generalization of a graph in which an
edge can connect any number of vertices. Formally, a
hypergraph H is a pair H=(X, E) where X is a set of elements
called nodes or vertices, and E is a set of non-empty subsets of
X called hyperedges or edges. Therefore, E is a nonempty
subset of P(X), where P(X) is the power set of X.
Definition 2.1
[8]
The correlation matrix of a hypernetwork
H=(X, E) is a matrix C(H)=(c
ij
)
|X
_h
|E|
with |X| rows and |E|
columns, where c
ij
=1 if x
i
ęe
j
, and c
ij
= 0 otherwise.
Since every row is in correspondence to one node and every
column represents one hyperedge, the correlation matrix is
usually considered as a partitioned matrix.
2015 International Conference on Intelligent Systems and Knowledge Engineering
978-1-4673-9323-2/15 $31.00 © 2015 European Union
DOI 10.1109/ISKE.2015.24
176