3
3.0

Jun 29, 2018
06/18

by
Linyuan Lü; Duanbing Chen; Xiao-Long Ren; Qian-Ming Zhang; Yi-Cheng Zhang; Tao Zhou

texts

#
eye 3

#
favorite 0

#
comment 0

Real networks exhibit heterogeneous nature with nodes playing far different roles in structure and function. To identify vital nodes is thus very significant, allowing us to control the outbreak of epidemics, to conduct advertisements for e-commercial products, to predict popular scientific publications, and so on. The vital nodes identification attracts increasing attentions from both computer science and physical societies, with algorithms ranging from simply counting the immediate neighbors...

Topics: Social and Information Networks, Computing Research Repository, Physics, Physics and Society

Source: http://arxiv.org/abs/1607.01134

5
5.0

Jun 30, 2018
06/18

by
Linyuan Lu; Shoudong Man

texts

#
eye 5

#
favorite 0

#
comment 0

In 1970 Smith classified all connected graphs with the spectral radius at most $2$. Here the spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Recently, the definition of spectral radius has been extended to $r$-uniform hypergraphs. In this paper, we generalize the Smith's theorem to $r$-uniform hypergraphs. We show that the smallest limit point of the spectral radii of connected $r$-uniform hypergraphs is $\rho_r=(r-1)!\sqrt[r]{4}$. We discovered a novel method for...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1402.5402

45
45

Sep 19, 2013
09/13

by
Jerrold R. Griggs; Wei-Tian Li; Linyuan Lu

texts

#
eye 45

#
favorite 0

#
comment 0

Given a finite poset P, we consider the largest size La(n,P) of a family of subsets of $[n]:=\{1,...,n\}$ that contains no subposet P. This problem has been studied intensively in recent years, and it is conjectured that $\pi(P):= \lim_{n\rightarrow\infty} La(n,P)/{n choose n/2}$ exists for general posets P, and, moreover, it is an integer. For $k\ge2$ let $\D_k$ denote the $k$-diamond poset $\{A < B_1,...,B_k < C\}$. We study the average number of times a random full chain meets a...

Source: http://arxiv.org/abs/1010.5311v3

2
2.0

Jun 30, 2018
06/18

by
Linyuan Lu; Xing Peng

texts

#
eye 2

#
favorite 0

#
comment 0

In this paper, we study the high-order phase transition in random $r$-uniform hypergraphs. For a positive integer $n$ and a real $p\in [0,1]$, let $H:=H^r(n,p)$ be the random $r$-uniform hypergraph on the vertex set $[n]$, where each $r$-set is an edge with probability $p$ independently. For $1\leq s \leq r-1$ and two $s$-sets $S$ and $S'$, we say $S$ is connected to $S'$ if there is a sequence of alternating $s$-sets and edges $S_0,F_1,S_1,F_2, \ldots, F_k, S_k$ which satisfies...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1409.1174

53
53

Sep 23, 2013
09/13

by
Qian-Ming Zhang; Linyuan Lü; Wen-Qiang Wang; Yu-Xiao Zhu; Tao Zhou

texts

#
eye 53

#
favorite 0

#
comment 0

Uncovering factors underlying the network formation is a long-standing challenge for data mining and network analysis. In particular, the microscopic organizing principles of directed networks are less understood than those of undirected networks. This article proposes a hypothesis named potential theory, which assumes that every directed link corresponds to a decrease of a unit potential and subgraphs with definable potential values for all nodes are preferred. Combining the potential theory...

Source: http://arxiv.org/abs/1202.2709v2

2
2.0

Jun 30, 2018
06/18

by
Richard P. Anstee; Linyuan Lu

texts

#
eye 2

#
favorite 0

#
comment 0

Balogh and Bollob\'as [{\em Combinatorica 25, 2005}] prove that for any $k$ there is a constant $f(k)$ such that any set system with at least $f(k)$ sets reduces to a $k$-star, an $k$-costar or an $k$-chain. They proved $f(k)

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1409.4123

35
35

Sep 18, 2013
09/13

by
Steve Butler; Ron Graham; Linyuan Lu

texts

#
eye 35

#
favorite 0

#
comment 0

We consider the problem of coloring $[n]={1,2,...,n}$ with $r$ colors to minimize the number of monochromatic $k$ term arithmetic progressions (or $k$-APs for short). We show how to extend colorings of $\mathbb{Z}_m$ which avoid nontrivial $k$-APs to colorings of $[n]$ by an unrolling process. In particular, by using residues to color $\mathbb{Z}_m$ we produce the best known colorings for minimizing the number of monochromatic $k$-APs for coloring with $r$ colors for several small values of $r$...

Source: http://arxiv.org/abs/1209.2687v1

10
10.0

Jun 28, 2018
06/18

by
Linyuan Lu; Arthur L. B. Yang

texts

#
eye 10

#
favorite 0

#
comment 0

Let $f(m,c)=\sum_{k=0}^{\infty} (km+1)^{k-1} c^k e^{-c(km+1)/m} / (m^kk!)$. For any positive integer $m$ and positive real $c$, the identity $f(m,c)=f(1,c)^{1/m}$ arises in the random graph theory. In this paper, we present two elementary proofs of this identity: a pure combinatorial proof and a power-serial proof. We also proved that this identity holds for any positive reals $m$ and $c$.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1506.08382

5
5.0

Jun 30, 2018
06/18

by
Linyuan Lu; Kevin G. Milans

texts

#
eye 5

#
favorite 0

#
comment 0

Let $F$ be a family of subsets of $\{1,\ldots,n\}$. We say that $F$ is $P$-free if the inclusion order on $F$ does not contain $P$ as an induced subposet. The \emph{Tur\'an function} of $P$, denoted $\pi^*(n,P)$, is the maximum size of a $P$-free family of subsets of $\{1,\ldots,n\}$. We show that $\pi^*(n,P) \le (4r + O(\sqrt{r}))\binom{n}{n/2}$ if $P$ is an $r$-element poset of height at most $2$. We also show that $\pi^*(n,S_r) = (r+O(\sqrt{r}))\binom{n}{n/2}$ where $S_r$ is the standard...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1408.0646

136
136

Jul 24, 2013
07/13

by
Jerrold R. Griggs; Linyuan Lu

texts

#
eye 136

#
favorite 0

#
comment 0

Let $\F\subset 2^{[n]}$ be a family of subsets of $\{1,2,..., n\}$. For any poset $H$, we say $\F$ is $H$-free if $\F$ does not contain any subposet isomorphic to $H$. Katona and others have investigated the behavior of $\La(n,H)$, which denotes the maximum size of $H$-free families $\F\subset 2^{[n]}$. Here we use a new approach, which is to apply methods from extremal graph theory and probability theory to identify new classes of posets $H$, for which $\La(n,H)$ can be determined...

Source: http://arxiv.org/abs/0807.3702v1

3
3.0

Jun 30, 2018
06/18

by
Edward Boehnlein; Peter Chin; Amit Sinha; Linyuan Lu

texts

#
eye 3

#
favorite 0

#
comment 0

The diffusion state distance (DSD) was introduced by Cao-Zhang-Park-Daniels-Crovella-Cowen-Hescott [{\em PLoS ONE, 2013}] to capture functional similarity in protein-protein interaction networks. They proved the convergence of DSD for non-bipartite graphs. In this paper, we extend the DSD to bipartite graphs using lazy-random walks and consider the general $L_q$-version of DSD. We discovered the connection between the DSD $L_q$-distance and Green's function, which was studied by Chung and Yau...

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1410.3168

49
49

Sep 21, 2013
09/13

by
Linyuan Lu; Laszlo A. Szekely

texts

#
eye 49

#
favorite 0

#
comment 0

Our previous paper applied a lopsided version of the Lov\'asz Local Lemma that allows negative dependency graphs to the space of random injections from an $m$-element set to an $n$-element set. Equivalently, the same story can be told about the space of random matchings in $K_{n,m}$. Now we show how the cited version of the Lov\'asz Local Lemma applies to the space of random matchings in $K_{2n}$. We also prove tight upper bounds that asymptotically match the lower bound given by the Lov\'asz...

Source: http://arxiv.org/abs/0905.3983v3

42
42

Sep 21, 2013
09/13

by
An Zeng; Linyuan Lü; Tao Zhou

texts

#
eye 42

#
favorite 0

#
comment 0

In this paper, we studied the strategies to enhance synchronization on directed networks by manipulating a fixed number of links. We proposed a centrality-based reconstructing (CBR) method, where the node centrality is measured by the well-known PageRank algorithm. Extensive numerical simulation on many modeled networks demonstrated that the CBR method is more effective in facilitating synchronization than the degree-based reconstructing method and random reconstructing method for adding or...

Source: http://arxiv.org/abs/1106.5906v1

4
4.0

Jun 30, 2018
06/18

by
Zhi-Qiang You; Xiao-Pu Han; Linyuan Lü; Chi Ho Yeung

texts

#
eye 4

#
favorite 0

#
comment 0

Participation in social groups are important but the collective behaviors of human as a group are difficult to analyze due to the difficulties to quantify ordinary social relation, group membership, and to collect a comprehensive dataset. Such difficulties can be circumvented by analyzing online social networks. In this paper, we analyze a comprehensive dataset obtained from Tencent QQ, an instant messenger with the highest market share in China. Specifically, we analyze three derivative...

Topics: Physics, Physics and Society, Computing Research Repository, Social and Information Networks

Source: http://arxiv.org/abs/1408.5558

60
60

Jul 20, 2013
07/13

by
Linyuan Lu; Xing Peng

texts

#
eye 60

#
favorite 0

#
comment 0

This paper is motivated by a recent result of Wolf \cite{wolf} on the minimum number of monochromatic 4-term arithmetic progressions(4-APs, for short) in $\Z_p$, where $p$ is a prime number. Wolf proved that there is a 2-coloring of $\Z_p$ with 0.000386% fewer monochromatic 4-APs than random 2-colorings; the proof is probabilistic and non-constructive. In this paper, we present an explicit and simple construction of a 2-coloring with 9.3% fewer monochromatic 4-APs than random 2-colorings. This...

Source: http://arxiv.org/abs/1107.2888v1

3
3.0

Jun 30, 2018
06/18

by
Travis Johnston; Linyuan Lu

texts

#
eye 3

#
favorite 0

#
comment 0

The hypergraph jump problem and the study of Lagrangians of uniform hypergraphs are two classical areas of study in the extremal graph theory. In this paper, we refine the concept of jumps to strong jumps and consider the analogous problems over non-uniform hypergraphs. Strong jumps have rich topological and algebraic structures. The non-strong-jump values are precisely the densities of the hereditary properties, which include the Tur\'an densities of families of hypergraphs as special cases....

Topics: Mathematics, Combinatorics

Source: http://arxiv.org/abs/1403.1220

3
3.0

Jun 30, 2018
06/18

by
Linyuan Lu; Shoudong Man

texts

#
eye 3

#
favorite 0

#
comment 0

In our previous paper, we classified all $r$-uniform hypergraphs with spectral radius at most $(r-1)!\sqrt[r]{4}$, which directly generalizes Smith's theorem for the graph case $r=2$. It is nature to ask the structures of the hypergraphs with spectral radius slightly beyond $(r-1)!\sqrt[r]{4}$. For $r=2$, the graphs with spectral radius at most $\sqrt{2+\sqrt{5}}$ are classified by [{\em Brouwer-Neumaier, Linear Algebra Appl., 1989}]. Here we consider the $r$-uniform hypergraphs $H$ with...

Topics: Mathematics, Spectral Theory, Combinatorics

Source: http://arxiv.org/abs/1412.1270

12
12

Jun 28, 2018
06/18

by
Shenggong Ji; Linyuan Lu; Chi Ho Yeung; Yanqing Hu

texts

#
eye 12

#
favorite 0

#
comment 0

Social networks constitute a new platform for information propagation, but its success is crucially dependent on the choice of spreaders who initiate the spreading of information. In this paper, we remove edges in a network at random and the network segments into isolated clusters. The most important nodes in each cluster then form a group of influential spreaders, such that news propagating from them would lead to an extensive coverage and minimal redundancy. The method well utilizes the...

Topics: Social and Information Networks, Physics and Society, Computing Research Repository, Physics

Source: http://arxiv.org/abs/1508.04294

64
64

Sep 21, 2013
09/13

by
Linyuan Lu; Xing Peng

texts

#
eye 64

#
favorite 0

#
comment 0

Let $G$ be any triangle-free graph with maximum degree $\Delta\leq 3$. Staton proved that the independence number of $G$ is at least 5/14n. Heckman and Thomas conjectured that Staton's result can be strengthened into a bound on the fractional chromatic number of $G$, namely $\chi_f(G)\leq 14/5. Recently, Hatami and Zhu proved $\chi_f(G) \leq 3 -{3/64}$. In this paper, we prove $\chi_f(G) \leq 3- 3/43$.

Source: http://arxiv.org/abs/1011.2500v2

57
57

Sep 19, 2013
09/13

by
Linyuan Lu; Tao Zhou

texts

#
eye 57

#
favorite 0

#
comment 0

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also...

Source: http://arxiv.org/abs/1010.0725v1

48
48

Sep 23, 2013
09/13

by
Jingfen Lan; Linyuan Lu; Lingsheng Shi

texts

#
eye 48

#
favorite 0

#
comment 0

The spectral radius $\rho(G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix $A(G)$. For a fixed integer $e\ge 1$, let $G^{min}_{n,n-e}$ be a graph with minimal spectral radius among all connected graphs on $n$ vertices with diameter $n-e$. Let $P_{n_1,n_2,...,n_t,p}^{m_1,m_2,...,m_t}$ be a tree obtained from a path of $p$ vertices ($0 \sim 1 \sim 2 \sim ... \sim (p-1)$) by linking one pendant path $P_{n_i}$ at $m_i$ for each $i\in\{1,2,...,t\}$. For $e=1,2,3,4,5$,...

Source: http://arxiv.org/abs/1110.2444v1

32
32

Sep 22, 2013
09/13

by
Linyuan Lu; Yi-Cheng Zhang; Chi Ho Yeung; Tao Zhou

texts

#
eye 32

#
favorite 0

#
comment 0

Finding pertinent information is not limited to search engines. Online communities can amplify the influence of a small number of power users for the benefit of all other users. Users' information foraging in depth and breadth can be greatly enhanced by choosing suitable leaders. For instance in delicious.com, users subscribe to leaders' collection which lead to a deeper and wider reach not achievable with search engines. To consolidate such collective search, it is essential to utilize the...

Source: http://arxiv.org/abs/1103.5231v1

58
58

Sep 21, 2013
09/13

by
Yong Lin; Linyuan Lu; S. -T. Yau

texts

#
eye 58

#
favorite 0

#
comment 0

A graph is called Ricci-flat if its Ricci-curvatures vanish on all edges. Here we use the definition of Ricci-cruvature on graphs given in [Lin-Lu-Yau, Tohoku Math., 2011], which is a variation of [Ollivier, J. Funct. Math., 2009]. In this paper, we classified all Ricci-flat connected graphs with girth at least five: they are the infinite path, cycle $C_n$ ($n\geq 6$), the dodecahedral graph, the Petersen graph, and the half-dodecahedral graph. We also construct many Ricci-flat graphs with...

Source: http://arxiv.org/abs/1301.0102v1

50
50

Sep 23, 2013
09/13

by
Yan-Bo Zhou; Linyuan Lü; Menghui Li

texts

#
eye 50

#
favorite 0

#
comment 0

The number of citations is a widely used metric to evaluate the scientific credit of papers, scientists and journals. However, it does happen that a paper with fewer citations from prestigious scientists is of higher influence than papers with more citations. In this paper, we argue that from whom the paper is being cited is of higher significance than merely the number of received citations. Accordingly, we propose an interactive model on author-paper bipartite networks as well as an iterative...

Source: http://arxiv.org/abs/1109.1186v2

52
52

Sep 23, 2013
09/13

by
Linyuan Lu; Xing Peng

texts

#
eye 52

#
favorite 0

#
comment 0

Let $H=(V,E)$ be an $r$-uniform hypergraph with the vertex set $V$ and the edge set $E$. For $1\leq s \leq r/2$, we define a weighted graph $G^{(s)}$ on the vertex set ${V\choose s}$ as follows. Every pair of $s$-sets $I$ and $J$ is associated with a weight $w(I,J)$, which is the number of edges in $H$ passing through $I$ and $J$ if $I\cap J=\emptyset$, and 0 if $I\cap J\not=\emptyset$. The $s$-th Laplacian $\L^{(s)}$ of $H$ is defined to be the normalized Laplacian of $G^{(s)}$. The...

Source: http://arxiv.org/abs/1109.3433v3

38
38

Sep 21, 2013
09/13

by
Linyuan Lü; Matus Medo; Yi-Cheng Zhang

texts

#
eye 38

#
favorite 0

#
comment 0

We consider a simple market where a vendor offers multiple variants of a certain product and preferences of both the vendor and potential buyers are heterogeneous and possibly even antagonistic. Optimization of the joint benefit of the vendor and the buyers turns the toy market into a combinatorial matching problem. We compare the optimal solutions found with and without a matchmaker, examine the resulting inequality between the market participants, and study the impact of correlations on the...

Source: http://arxiv.org/abs/0902.0504v2

49
49

Sep 23, 2013
09/13

by
Jingfen Lan; Linyuan Lu

texts

#
eye 49

#
favorite 0

#
comment 0

The spectral radius $\rho(G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph $G$ with $\rho(G)\leq 3/2{\sqrt{2}}$ is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radius greater than $3/2{\sqrt{2}}$. In this paper we proved the following results. For any open quipu $G$ on $n$ vertices ($n\geq 6$) with spectral radius less than...

Source: http://arxiv.org/abs/1112.4947v1

67
67

Sep 21, 2013
09/13

by
Yu-Xiao Zhu; Linyuan Lü; Qian-Ming Zhang; Tao Zhou

texts

#
eye 67

#
favorite 0

#
comment 0

To evaluate the performance of prediction of missing links, the known data are randomly divided into two parts, the training set and the probe set. We argue that this straightforward and standard method may lead to terrible bias, since in real biological and information networks, missing links are more likely to be links connecting low-degree nodes. We therefore study how to uncover missing links with low-degree nodes, namely links in the probe set are of lower degree products than a random...

Source: http://arxiv.org/abs/1104.0395v2

49
49

Jul 20, 2013
07/13

by
Linyuan Lü; Matus Medo; Yi-Cheng Zhang; Damien Challet

texts

#
eye 49

#
favorite 0

#
comment 0

We introduce a fully probabilistic framework of consumer product choice based on quality assessment. It allows us to capture many aspects of marketing such as partial information asymmetry, quality differentiation, and product placement in a supermarket.

Source: http://arxiv.org/abs/0804.1229v2

98
98

Sep 21, 2013
09/13

by
Yiting Yang; Linyuan Lu

texts

#
eye 98

#
favorite 0

#
comment 0

The {\it Randi\'c index} $R(G)$ of a graph $G$ is defined as the sum of 1/\sqrt{d_ud_v} over all edges $uv$ of $G$, where $d_u$ and $d_v$ are the degrees of vertices $u$ and $v,$ respectively. Let $D(G)$ be the diameter of $G$ when $G$ is connected. Aouchiche-Hansen-Zheng conjectured that among all connected graphs $G$ on $n$ vertices the path $P_n$ achieves the minimum values for both $R(G)/D(G)$ and $R(G)- D(G)$. We prove this conjecture completely. In fact, we prove a stronger theorem: If...

Source: http://arxiv.org/abs/1104.0426v1

104
104

Sep 23, 2013
09/13

by
Linyuan Lü; Matus Medo; Chi Ho Yeung; Yi-Cheng Zhang; Zi-Ke Zhang; Tao Zhou

texts

#
eye 104

#
favorite 0

#
comment 0

The ongoing rapid expansion of the Internet greatly increases the necessity of effective recommender systems for filtering the abundant information. Extensive research for recommender systems is conducted by a broad range of communities including social and computer scientists, physicists, and interdisciplinary researchers. Despite substantial theoretical and practical achievements, unification and comparison of different approaches are lacking, which impedes further advances. In this article,...

Source: http://arxiv.org/abs/1202.1112v1

112
112

Jul 20, 2013
07/13

by
Linyuan Lü; Duan-Bing Chen; Tao Zhou

texts

#
eye 112

#
favorite 0

#
comment 0

Spreading dynamics of information and diseases are usually analyzed by using a unified framework and analogous models. In this paper, we propose a model to emphasize the essential difference between information spreading and epidemic spreading, where the memory effects, the social reinforcement and the non-redundancy of contacts are taken into account. Under certain conditions, the information spreads faster and broader in regular networks than in random networks, which to some extent supports...

Source: http://arxiv.org/abs/1107.0429v2

82
82

Jun 29, 2018
06/18

by
Max Land; Linyuan Lu

texts

#
eye 82

#
favorite 0

#
comment 0

The burning number $b(G)$ of a graph $G$ was introduced by Bonato, Janssen, and Roshanbin [Lecture Notes in Computer Science 8882 (2014)] for measuring the speed of the spread of contagion in a graph. They proved for any connected graph $G$ of order $n$, $b(G)\leq 2\lceil \sqrt{n} \rceil-1$, and conjectured that $b(G)\leq \lceil \sqrt{n} \rceil$. In this paper, we proved $b(G)\leq \lceil\frac{-3+\sqrt{24n+33}}{4}\rceil$, which is roughly $\frac{\sqrt{6}}{2}\sqrt{n}$. We also settled the...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1606.07614

83
83

Sep 17, 2013
09/13

by
Qian-Ming Zhang; Ming-Sheng Shang; Linyuan Lu

texts

#
eye 83

#
favorite 0

#
comment 0

We propose a similarity-based method, using the similarity between nodes, to address the problem of classification in partially labeled networks. The basic assumption is that two nodes are more likely to be categorized into the same class if they are more similar. In this paper, we introduce ten similarity indices, including five local ones and five global ones. Empirical results on the co-purchase network of political books show that the similarity-based method can give high accurate...

Source: http://arxiv.org/abs/1003.0837v1

50
50

Sep 21, 2013
09/13

by
Tao Zhou; Linyuan Lu; Yi-Cheng Zhang

texts

#
eye 50

#
favorite 0

#
comment 0

Missing link prediction of networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely common neighbors, has the best overall performance, and the Adamic-Adar index performs the second best. A new similarity measure, motivated by...

Source: http://arxiv.org/abs/0901.0553v2

37
37

Sep 22, 2013
09/13

by
Andrew D. King; Linyuan Lu; Xing Peng

texts

#
eye 37

#
favorite 0

#
comment 0

Let $\Delta(G)$ be the maximum degree of a graph $G$. Brooks' theorem states that the only connected graphs with chromatic number $\chi(G)=\Delta(G)+1$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs $G$ such that the fractional chromatic number $\chi_f(G)$ is at least $\Delta(G)$. These graphs are complete graphs, odd cycles, $C^2_8$, $C_5\boxtimes K_2$, and graphs whose clique number $\omega(G)$...

Source: http://arxiv.org/abs/1103.3524v3

67
67

Sep 18, 2013
09/13

by
Linyuan Lu; Weiping Liu

texts

#
eye 67

#
favorite 0

#
comment 0

Recommender systems have shown great potential to address information overload problem, namely to help users in finding interesting and relevant objects within a huge information space. Some physical dynamics, including heat conduction process and mass or energy diffusion on networks, have recently found applications in personalized recommendation. Most of the previous studies focus overwhelmingly on recommendation accuracy as the only important factor, while overlook the significance of...

Source: http://arxiv.org/abs/1102.5499v1

54
54

Sep 18, 2013
09/13

by
Linyuan Lu; Xing Peng

texts

#
eye 54

#
favorite 0

#
comment 0

Despite of the extreme success of the spectral graph theory, there are relatively few papers applying spectral analysis to hypergraphs. Chung first introduced Laplacians for regular hypergraphs and showed some useful applications. Other researchers treated hypergraphs as weighted graphs and then studied the Laplacians of the corresponding weighted graphs. In this paper, we aim to unify these very different versions of Laplacians for hypergraphs. We introduce a set of Laplacians for hypergraphs...

Source: http://arxiv.org/abs/1102.4409v1

52
52

Sep 21, 2013
09/13

by
Linyuan Lu; Xing Peng

texts

#
eye 52

#
favorite 0

#
comment 0

Let $G$ be a random graph on the vertex set $\{1,2,..., n\}$ such that edges in $G$ are determined by independent random indicator variables, while the probability $p_{ij}$ for $\{i,j\}$ being an edge in $G$ is not assumed to be equal. Spectra of the adjacency matrix and the normalized Laplacian matrix of $G$ are recently studied by Oliveira and Chung-Radcliffe. Let $A$ be the adjacency matrix of $G$, $\bar A=\E(A)$, and $\Delta$ be the maximum expected degree of $G$. Oliveira first proved that...

Source: http://arxiv.org/abs/1204.6207v1

44
44

Sep 19, 2013
09/13

by
Mingsheng Shang; Linyuan Lu; Yi-Cheng Zhang; Tao Zhou

texts

#
eye 44

#
favorite 0

#
comment 0

Understanding the structure and evolution of web-based user-object networks is a significant task since they play a crucial role in e-commerce nowadays. This Letter reports the empirical analysis on two large-scale web sites, audioscrobbler.com and del.icio.us, where users are connected with music groups and bookmarks, respectively. The degree distributions and degree-degree correlations for both users and objects are reported. We propose a new index, named collaborative clustering coefficient,...

Source: http://arxiv.org/abs/0909.4938v2

65
65

Sep 23, 2013
09/13

by
Linyuan Lu; Zi-Ke Zhang; Tao Zhou

texts

#
eye 65

#
favorite 0

#
comment 0

Zipf's law on word frequency is observed in English, French, Spanish, Italian, and so on, yet it does not hold for Chinese, Japanese or Korean characters. A model for writing process is proposed to explain the above difference, which takes into account the effects of finite vocabulary size. Experiments, simulations and analytical solution agree well with each other. The results show that the frequency distribution follows a power law with exponent being equal to 1, at which the corresponding...

Source: http://arxiv.org/abs/1202.2903v1

48
48

Sep 23, 2013
09/13

by
Zhen Liu; Qian-Ming Zhang; Linyuan Lü; Tao Zhou

texts

#
eye 48

#
favorite 0

#
comment 0

Common-neighbor-based method is simple yet effective to predict missing links, which assume that two nodes are more likely to be connected if they have more common neighbors. In such method, each common neighbor of two nodes contributes equally to the connection likelihood. In this Letter, we argue that different common neighbors may play different roles and thus lead to different contributions, and propose a local na\"{\i}ve Bayes model accordingly. Extensive experiments were carried out...

Source: http://arxiv.org/abs/1105.4005v1

65
65

Jul 20, 2013
07/13

by
Giulio Cimini; Duanbing Chen; Matus Medo; Linyuan Lu; Yi-Cheng Zhang; Tao Zhou

texts

#
eye 65

#
favorite 0

#
comment 0

The advent of Internet and World Wide Web has led to unprecedent growth of the information available. People usually face the information overload by following a limited number of sources which best fit their interests. It has thus become important to address issues like who gets followed and how to allow people to discover new and better information sources. In this paper we conduct an empirical analysis on different on-line social networking sites, and draw inspiration from its results to...

Source: http://arxiv.org/abs/1107.4491v2

84
84

Sep 21, 2013
09/13

by
Travis Johnston; Linyuan Lu

texts

#
eye 84

#
favorite 0

#
comment 0

A non-uniform hypergraph $H=(V,E)$ consists of a vertex set $V$ and an edge set $E\subseteq 2^V$; the edges in $E$ are not required to all have the same cardinality. The set of all cardinalities of edges in $H$ is denoted by $R(H)$, the set of edge types. For a fixed hypergraph $H$, the Tur\'an density $\pi(H)$ is defined to be $\lim_{n\to\infty}\max_{G_n}h_n(G_n)$, where the maximum is taken over all $H$-free hypergraphs $G_n$ on $n$ vertices satisfying $R(G_n)\subseteq R(H)$, and $h_n(G_n)$,...

Source: http://arxiv.org/abs/1301.1870v1

65
65

Sep 23, 2013
09/13

by
Richard P. Anstee; Linyuan Lu

texts

#
eye 65

#
favorite 0

#
comment 0

Let $t\ge 1$ be a given integer. Let ${\cal F}$ be a family of subsets of $[m]=\{1,2,\ldots,m\}$. Assume that for every pair of disjoint sets $S,T\subset [m]$ with $|S|=|T|=k$, there do not exist $2t$ sets in ${\cal F}$ where $t$ subsets of ${\cal F}$ contain $S$ and are disjoint from $T$ and $t$ subsets of ${\cal F}$ contain $T$ and are disjoint from $S$. We show that $|{\cal F}|$ is $O(m^{k})$. Our main new ingredient is allowing, during the inductive proof, multisets of subsets of $[m]$...

Source: http://arxiv.org/abs/1305.0603v1

51
51

Sep 20, 2013
09/13

by
Linyuan Lu; Zi-Ke Zhang; Tao Zhou

texts

#
eye 51

#
favorite 0

#
comment 0

Background: Zipf's law and Heaps' law are observed in disparate complex systems. Of particular interests, these two laws often appear together. Many theoretical models and analyses are performed to understand their co-occurrence in real systems, but it still lacks a clear picture about their relation. Methodology/Principal Findings: We show that the Heaps' law can be considered as a derivative phenomenon if the system obeys the Zipf's law. Furthermore, we refine the known approximate solution...

Source: http://arxiv.org/abs/1002.3861v2

55
55

Sep 22, 2013
09/13

by
Weiping Liu; Linyuan Lu

texts

#
eye 55

#
favorite 0

#
comment 0

The problem of missing link prediction in complex networks has attracted much attention recently. Two difficulties in link prediction are the sparsity and huge size of the target networks. Therefore, the design of an efficient and effective method is of both theoretical interests and practical significance. In this Letter, we proposed a method based on local random walk, which can give competitively good prediction or even better prediction than other random-walk-based methods while has a lower...

Source: http://arxiv.org/abs/1001.2467v1

43
43

Sep 23, 2013
09/13

by
An Zeng; Linyuan Lu

texts

#
eye 43

#
favorite 0

#
comment 0

Coarse graining model is a promising way to analyze and visualize large-scale networks. The coarse-grained networks are required to preserve the same statistical properties as well as the dynamic behaviors as the initial networks. Some methods have been proposed and found effective in undirected networks, while the study on coarse graining in directed networks lacks of consideration. In this paper, we proposed a Topology-aware Coarse Graining (TCG) method to coarse grain the directed networks....

Source: http://arxiv.org/abs/1012.0196v2