SIAM News Blog

From SIAM Review: SIGEST

SIGEST highlights a recent paper from one of SIAM's specialized research journals, chosen on the basis of exceptional interest to the entire SIAM community and revised and condensed as needed for greater accessibility. Read about the SIGEST paper in the latest SIAM Review and reasons why it was picked.

The field of network science, which is closely aligned with more traditional areas such as graph theory, linear algebra, random matrix theory, and discrete optimization, is gathering significant momentum within the SIAM community. Indeed, SIAM has supported a Workshop on Network Science each year since 2013. In 2017, this event ran alongside the Annual Meeting in Pittsburgh, featuring two full days of talks and 83 posters. SIAM Review has reflected this growing interest, with a number of high-profile articles appearing in recent years. A notable early example is Mark Newman's 2003 survey “The Structure and Function of Complex Networks” (volume 45, pages 167--256). This article brought the SIAM readership up-to-date on concepts such as the small-world effect, scale-free degree distributions, clustering, preferential attachment, random graph models, network growth, and dynamical processes on networks. At the time of writing, this survey has collected over 16,000 Google Scholar citations.

There are two main driving forces behind the rise of network science. First, increasing levels of digitization give us access to rich, large-scale sources of data. Second, greater computer power makes it feasible to handle this data. A typical problem setup involves some sort of dimension reduction; for example, finding well-connected communities, identifying the most important network nodes and connections, or ranking all nodes in terms of their importance. The highlighted SIGEST article in this issue, “Core-Periphery Structure in Networks (Revisited),” by Puck Rombach, Mason A. Porter, James H. Fowler, and Peter J. Mucha, considers an interesting twist that touches on all three of these tasks. Figure 1.1 illustrates the idea. In Figure 1.1(a), the network nodes have been ordered in such a way that a clear community structure is revealed through a diagonal block matrix structure. In some application fields, that type of pattern is less likely to be present, or is of less interest, than the arrangement in Figure 1.1(b). Here, we have a well-connected central core of nodes, corresponding to the (1,1) block. But this core is also well connected to the remaining, peripheral nodes. Researchers in numerical linear algebra will spot immediate overlap with ideas in sparse matrix reordering, but the motivation here is to reveal and quantify structure rather than to make subsequent computations more efficient.

Figure Figure 1.1 from the paper illustrates examples of network block models. (a) Community structure, (b) core-periphery structure, (c) global core-periphery structure with local community structure, and (d) global community structure with local core-periphery structure. Note that (c) and (d) are equivalent

The authors explain how this task arose in the study of social networks, and, building on that work, they set up a new optimization problem. Ultimately, their algorithm assigns a core score to each node, which can be used to distinguish between core and peripheral members, or, via node reordering, to visualize the overall structure. Examples are given on a range of real networks.

The original version of the article appeared in the SIAM Journal on Applied Mathematics in 2014. We are grateful to the authors for updating the contents and providing additional material for a nonspecialist readership. In particular, section 2 emphasizes the main aims of work, and section 3 discusses subsequent developments in this fast-moving field.

--From the editors of SIAM Review

blog comments powered by Disqus