Finding information source in viral spreading has important applications such as to root out the culprit of a rumor spreading in online social networks. In particular, given a snapshot observation of the rumor graph, how to accurately identify the initial source of the spreading? In the seminal work by Shah and Zaman in 2011, this statistical inference problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular. This however is optimal only if there are no boundary effects, e.g., the underlying number of susceptible vertices is countably infinite. In general, all practical real world networks are finite or exhibit complex spreading behavior, and therefore these boundary effects cannot be ignored. In this paper, we solve the constrained maximum likelihood estimation problem by a generalized rumor centrality for spreading in graphs with boundary effects. We derive a graph-theoretic characterization of the maximum likelihood estimator for degree-regular graphs with a single end vertex at its boundary and propose a message-passing algorithm that is near-optimal for graphs with more complex boundary consisting of multiple end vertices.

Detecting information source in viral spreading has important applications such as to root out the culprit of a rumor spreading in online social networks. In particular, given a snapshot observation of the network topology of nodes having the rumor, how to accurately identify the initial source of the spreading? In the seminal work [Shah et el. 2011], this problem was formulated as a maximum likelihood estimation problem and solved using a rumor centrality approach for graphs that are degree-regular trees. The case of graphs with cycles is an open problem. In this paper, we address the maximum likelihood estimation problem by a generalized rumor centrality for spreading in unicyclic graphs. In particular, we derive a generalized rumor centrality that leads to a new graph-theoretic design approach to inference algorithms.

Data centers play an important role in today's Internet development. Research to find scalable architecture and efficient routing algorithms for data center networks has gained popularity. The fat-tree architecture, which is essentially a folded version of a Clos network, has proved to be readily implementable and is scalable. In this paper, we investigate routing on a fat-tree network by deriving its global packing number and by presenting explicit algorithms for the construction of optimal, load-balanced routing solutions. Consider an optical network that employs wavelength division multiplexing in which every user node sets up a connection with every other user node. The global packing number is basically the number of wavelengths required by the network to support such a traffic load, under the restriction that each source-to-destination connection is assigned a wavelength that remains constant in the network. In mathematical terms, consider a bidirectional, simple graph, G and let N ⊆ V(G) be a set of nodes. A path system P of G with respect to N consists of |N|(|N| -1) directed paths, one path to connect each of the source-destination node pairs in N. The global packing number of a path system P, denoted by Φ(G, N, P), is the minimum integer k to guarantee the existence of a mapping φ : P → (1, 2, ..., k), such that φ(P) ≠ φ(P̅) if P and P̅ have common arc(s). The global packing number of (G, N), denoted by Φ(G, N), is defined to be the minimum Φ(G, N, P) among all possible path systems ?. In additional to wavelength division optical networks, this number also carries significance for networks employing time division multiple access. In this paper, we compute by explicit route construction the global packing number of (Tn, N), where Tndenotes the topology of the n-ary fat-tree network, and N is considered to be the set of all edge switches or the set of all supported hosts. We show that the constructed routes are load-balanced and require minimal link capacity at all network links.

Let $$\mathbb{C }$$ be a code of length $$n$$ over an alphabet of $$q$$ letters. The descendant code $$\mathsf{desc}(\mathbb C _0)$$ of $$\mathbb C _0 = \{\mathbf{c}^1, \mathbf{c}^2, \ldots , \mathbf{c}^t\} \subseteq \mathbb{C }$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)$$ such that $$x_i \in \{c^1_i, c^2_i, \ldots , c^t_i\}$$ for all $$i=1, \ldots , n$$ . $$\mathbb{C }$$ is a $$\overline{t}$$ -separable code if for any two distinct $$\mathbb{C }_1, \mathbb{C }_2 \subseteq \mathbb{C }$$ such that $$|\mathbb{C }_1| \le t$$ , $$|\mathbb{C }_2| \le t$$ , we always have $$\mathsf{desc}(\mathbb{C }_1) \ne \mathsf{desc}(\mathbb{C }_2)$$ . The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let $$M(\overline{t},n,q)$$ be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for $$M(\overline{2},2,q)$$ by a graph theoretical approach, and a new lower bound for $$M(\overline{2},2,q)$$ by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth $$6$$ and a construction of such maximal bipartite graphs.

In the above titled paper (ibid., vol. 56, pp. 5747-5756, Nov. 2010), the following corrections are necessary.

Direct constructions for optimal conflict-avoiding codes of length$n \equiv 4 \pmod{8}$and weight 3 are provided by bringing in a new concept called an extended odd sequence. Constructions for those odd sequences are also given in this paper. As a consequence, with previously known results, the spectrum of the size of optimal conflict-avoiding codes of even length and weight 3 is completely settled.

For a v-set V, let $\mathcal{A}$ be a collection of $r\times c$ arrays with elements in V. A pair $(V,\mathcal{A})$ is called an $r\times c$ grid-block design if every two distinct elements i and j in V occur exactly once in the same row or in the same column of an array in $\mathcal{A}$. This design originated from the use of DNA library screening. In this paper, we show the existence of $r\times 4$ grid-block designs with $r=3,4$. We settle completely for the case of $r=4$ and almost completely for the case of $r=3$, leaving 15 orders undetermined.

Abstract The generalized de Bruijn digraphGB(n,m) is the digraph (V,A) whereV= {0, 1,…,m− 1} and (i,j) ∈Aif and only ifj≡in+α(modm) for someα∈ {0, 1, 2,…,n− 1}. By replacing each arc ofGB(n,m) with an undirected edge and eliminating loops and multi‐edges, we obtain the generalized undirected de Bruijn graphUGB(n,m). In this article, we prove that when 2n2≤m≤n3the diameter ofUGB(n,m) is equal to 3. We also show that for pairs (n,m) wheren2<m< 2n2the diameter ofUGB(n,m) can be 2 or 3. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

In order to reduce the number of add-drop multiplexers (ADMs) in SONET/WDM networks using wavelength add-drop multiplexing, certain graph decompositions can be used to form a “grooming” that specifies the assignment of traffic to wavelengths. When traffic among nodes is all-to-all and uniform, the drop cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The number of ADMs required is this drop cost. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{7}$ of the wavelength capacity, is determined within an additive constant. Indeed when the number n of sites satisfies $n \equiv 1$ (mod 3) and $n \neq 19$, the determination is exact; when $n \equiv 0$ (mod 3), $n \not\equiv 18$ (mod 24), and n is large enough, the determination is also exact; and when $n \equiv 2$ (mod 3) and n is large enough, the gap between the cost of the best construction and the cost of the lower bound is independent of n and does not exceed 4.

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m (m \neq 2) vertices K 2m can be properly edge-colored with 2m - 1 colors in such a way that the edges of K 2m can be partitioned into m multicolored isomorphic spanning trees.

Fu, Hwang, Jimbo, Mutoh, and Shiue [J. Statist. Plann. Inference, to appear] introduced the concept of a grid-block design, which is defined as follows: For a v-set V, let ${\cal A}$ be a collection of r × c arrays with elements in V. A pair $(V, {\cal A})$ is called an r × cgrid-block design if every two distinct points i and j in V occur exactly once in the same row or in the same column. This design has originated from the use of DNA library screening. They gave some general constructions and proved the existence of 3×3 grid-block designs. Meanwhile, the existence of 2×3 grid-block designs was shown by Carter [ Designs on Cubic Multigraphs, Ph.D. thesis, McMaster University, Hamilton, ON, Canada, 1989] by decomposing K v into cubic graphs. In this paper, we show the existence of 2×4 grid-block designs.