Industry Applications of Network Science and Graph Algorithms

By Tamer Khraisha, Ph.D. in Network Science

Network science has emerged as an interdisciplinary field of research to leverage network data's increasing availability to investigate a wide range of complex phenomena such as collective social behavior, technological development, financial stability, biological interactions, and many more. Simply put, network data consists of entities known as nodes, and relations between them are known as links. Nodes can be persons, organizations, URLs, or proteins. Links can represent relations such as the friendship between persons, technological transfers between firms, hyperlinks between websites, and chemical interactions between proteins. Network science employs an extensive array of analytical methods and data science techniques borrowed from sociology, mathematics, physics, computer science, economics, and other fields.

Most current research in network science has focused on measurements and the construction of theoretical and data-driven models. Although less has been done on the industry side, there are several cases and areas in which network science has either been successfully employed or could potentially be applied. In this article, I will illustrate some of these applications and provide examples and references for further investigations.

Link Prediction and Recommender Systems

In network science, the nodes' links are the primary source of information about the patterns and complexity of the networks. In some cases, not all links are observed; therefore, we might be interested in predicting the missing links. Links might be missing for a variety of reasons; for example, a link might exist but is not recorded in the data, in which case the link prediction task consists of inferring the missing link. In other cases, the link might not exist in the first place, but we believe it makes sense for it to exist; In this case, the link prediction task concerns a recommendation of which new links to establish. Examples of industrial application of link-prediction based recommendation systems are abundant: recommending new friendships on social media, books on online shops, or movies. 

In the figure below, I provide a basic example of how network science can be employed in recommender systems. The illustrated graph is a bipartite graph with two types of nodes: users on the left and books on the right. A link between the user and a book indicates that the user bought the book. If we take user 1, we can observe that she purchased Book 1, Book 2, and Book 5. On the other hand, user 2 bought Book 1 and Book 2 but not Book 5. Given the apparent similarity in interest between users 1 and 2 (they both bought Book 1 and 2), we can assume that User 2 would be interested in Book 5. The blue link in the graph is what we would predict based on this logic.

Organizational Mapping

Theoretically speaking, organizations are often depicted as formal, hierarchical structures with clear interaction patterns. In reality, however, most of the work inside the organization is done via informal networks. In the informal organization, employees (the nodes) communicate, share knowledge, ask for advice, and plan initiatives. Given the vital role of these informal networks in the organization's functioning, interest has surged around the idea of mapping the organizational networks. Organizational mapping can help managers direct the informal networks, detect fragilities in the network structure, and allow collaboration.

The figure below (source here) illustrates some of the information that network organizational mapping can provide. For example, specific nodes might act as knowledge brokers or connectors between different groups; others assume a central/hub role, while others are more isolated/peripheral. With knowledge brokers, the manager might want to make sure they are up to date with relevant organizational matters or make sure that internal groups don't get disconnected if the broker goes on holiday. A hub node might be influential, and he/she could be assuming too much influence on the organization's various initiatives. A peripheral node might be a talented person who can contribute more to the organization if connected with more people. 

Competitive and Strategic Analysis

Due to competition and market dynamics, companies continuously observe and analyze their market landscape to achieve and maintain a strategic competitive advantage. A variety of approaches have been proposed to explain the drivers of competitive advantage; These include the firm's resource-based view, the knowledge-based view, composition-based view, dynamic capabilities, absorptive capabilities, and the relation-based view. 

In the relation-based approach, the firm and its performance are analyzed in relation to its strategic embeddedness into an inter-organizational network of firm alliances, partnerships, and other collaborations. In this regard, a firm can employ network science to analyze the network structure of market alliances and collaborations to embed itself in the inter-organizational network strategically and to understand the portfolios of alliances of its competitors. For example, to catch up with its competitive market, Huawei Technologies implemented a network strategy where they entered in collaboration with several firms and institutions to accelerate innovation. 

Customer Analysis

Companies are continually trying to understand and predict their client behavior to preserve and grow their customer base. To this end, companies use various business models and approaches, such as market analysis of the customer base. However, such practices are general and miss the micro-behavioral aspects of customers. An innovative approach relies on social network analysis to analyze the relations between customers and predict their behavior.

For example, T-Mobile USA, a telecommunication provider, has begun including social ties between subscribers to predict and manage customer churn, which is a severe problem for telecommunication providers. The main goal of T-Mobile’s social network model is to identify “influencers’, whose decision and choice might affect a significant number of other customers. By integrating social network analysis into its churn management system, T-Mobile achieved an almost 50% reduction in customer churn in the second quarter of 2011 compared with the first quarter of the same year.

Fraud Detection

Fraud detection is one of the most critical and challenging tasks in business. Activities that involve online transactions, cell phones, emails, insurance claims, tax return claims, credit card transactions are all subject to fraudulent behavior. A rich literature on this topic exists with various implementations and methods, among which is Network Science.

One way network science can help in fraud detection is by analyzing link patterns in the system. To provide a simplified example, let’s consider the fact that fraudsters nowadays are adaptive, in that they try to adjust their behavior based on the fraud detection policy of their targets. A company might try to detect suspicious activity by checking if it originates from the same account, address, zip code, and IP address. Knowing this, a fraudster might try to use multiple accounts with different information to deceive the company. By employing network science, it could be possible to analyze the account-information links to establish a connection between different accounts that belong to the same person who is engaged in fraudulent activity. The figure below illustrates the idea via a bipartite graph. From the chart, one can see that Accounts 1 and 2 share the same IP address but use different phone numbers, while Accounts 1 and 3 share the same phone number. This can be an indicator that all three accounts belong to the same person.

Search and information retrieval

In many contexts, information is stored as a network where nodes represent information pieces, and links encode relationships between them. Examples of such networks include the World Wide Web, patent and academic citations, and peer-to-peer networks. Crucially, the amount of data in such information networks can be considerable, and such data might be useless without some way of searching and finding specific items of interest. A quick look at the market clearly shows that the companies that provide search results are among the largest in their respective industries - e.g., Google, Thomson Reuters, Linkedin, and Amazon.

In performing fast and accurate searches, several network issues can be involved; Examples include web search algorithms such as PageRank, distributed database or file system search, sending messages from a source to a target, and finding suitable candidates for a job.

Knowledge Graphs

In the past few years, an essential development in internet-based information search has involved the concept of knowledge graphs. There is no clear definition of knowledge graphs; however, the main idea is to collect knowledge, content, and facts of different types and from multiple resources, aggregate them into a structured format, and use them to serve additional information when a user submits a search query. 

The power of knowledge graphs derives from the fact that they are very flexible graphs in that they can include multiple types of entities and various kinds of relations. This abundant amount of information can make search results more precise and uncover hidden data relationships that otherwise would not be detected with more straightforward methods. A variety of graph embedding techniques can be applied then to obtain lower-dimensional representations of the nodes and links in a knowledge graph.

The first knowledge graph was built by Google to enrich search query results with information gathered from various sources. The additional information is presented in an infobox next to the search results, as shown in the figure below (source here). At Amazon, a team of researchers is working on building a Product Graph, a knowledge graph to answer every question about products and related knowledge in the world.

Supply Chain Management and Flow Optimization

Among the various managerial problems in supply chain and logistics is finding the optimal route for distributing goods from sources to a final target destination. In this regard, the use of network science can help in visualizing and understanding the structure and dynamics of the managerial problems. Examples of such problems include:

1- The transportation problem deals with the distribution of goods from some points of supply (sources) to points of demand (destinations).

2- Facility Location Analysis investigates which location among several alternatives is best to locate a new facility.

3- The Assignment Problem involves determining the most efficient assignment of persons to projects, salespeople to territories, jobs to machines, patients to hospitals, and so on.

4- The Transshipment Problem is a transportation problem that involves an intermediate point (transshipment point) between the source and target.

5- The Maximal Flow Problem involves maximizing the amount of material or goods that can flow from one source to a target in a network.

6- The Shortest-Route Problem is concerned with finding the shortest distance from one source location to another.

7- The Minimum-Spanning Tree problem connects all points of a network while minimizing the total distance between them.

Other network science applications

1- Financial network analysis for financial stability policymaking.

2- Project and organizational complexity management.

3- Medicine and biological research.

4- Marketing and advertisement.

5- Urban planning and city mapping.

REFERENCES

Recommender Systems

Li, X., & Chen, H. (2013). Recommendation as link prediction in bipartite graphs: A graph kernel-based machine learning approach. Decision Support Systems, 54(2), 880-890.

Getoor, L., & Diehl, C. P. (2005). Link mining: a survey. Acm Sigkdd Explorations Newsletter, 7(2), 3-12.

Chen, H., Li, X., & Huang, Z. (2005, June). Link prediction approach to collaborative filtering. In Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL'05) (pp. 141-142). IEEE.

Lü, L., & Zhou, T. (2011). Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6), 1150-1170.

Organizational Mapping

Krackhardt, D., & Hanson, J. R. (2003). Informal Networks. Networks in the knowledge economy, 235.

Burt, R. S. (2009). Structural holes: The social structure of competition. Harvard university press.

Competitive and strategic analysis

Dyer, J.H., Singh, H. (1998): The relational view: Cooperative strategy and sources of interorganizational competitive advantage. Academy of Management Review, Vol. 23, pp. 660–679.

Greve, H., Rowley, T., & Shipilov, A. (2013). Network advantage: How to unlock value from your alliances and partnerships. John Wiley & Sons.

Zhang, Y. (2014). Catching-up by Chinese multinational firms using network strategies. In Successes and challenges of emerging economy multinationals (pp. 50-102). Palgrave Macmillan, London.

Fraud detection

Baesens, B., Van Vlasselaer, V., & Verbeke, W. (2015). Fraud analytics using descriptive, predictive, and social network techniques: a guide to data science for fraud detection. John Wiley & Sons.

Search and Information Retrieval

Newman, M. (2018). Networks. Oxford university press.

Knowledge Graphs

Fensel, Dieter, et al. Knowledge Graphs. Springer International Publishing, 2020.

Dong, X (2020), Building product graphs automatically, available here.

Google Blog (2012), Introducing the Knowledge Graph: things, not strings, available here

Supply Chain Management and Flow Optimization

Render, B., & Stair Jr, R. M. (2016). Quantitative Analysis for Management, 12e. Pearson Education India.