Network modality reduction

• US 10,171,307 B2
• Filed: 08/05/2016
• Issued: 01/01/2019
• Est. Priority Date: 08/05/2016
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Cawson, Michael G.
• Primary Examiner(s): Jacobs, Lashonda T
• Application Number:
  US15/229,894
• Publication Number:
  US 20180041397A1
• Time in Patent Office: 879 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0817 by checking functioning

Abstract

A tool for processing a multi-modal network to reduce modality. The tool determines a plurality of entities connected by a plurality of links within a multi-modal network. The tool assigns a weighted value to each of the plurality of links connecting the plurality of entities. The tool converts the multi-modal network into a modelled network based, at least in part, on the weighted value assigned to each of the plurality of links. The tool eliminates one or more of the plurality of entities not designated as an entity of interest from the modelled network. The tool converts the modelled network into a uni-modal network.

Claims

1. A method for processing a multi-modal network to reduce modality, the method comprising:

determining, by one or more computer processors, a plurality of entities connected by a plurality of links within a multi-modal network;

assigning, by the one or more processors, a weighted value to each of the plurality of links connecting the plurality of entities;

converting, by the one or more computer processors, the multi-modal network into a modelled network based, at least in part, on the weighted value assigned to each of the plurality of links;

eliminating, by the one or more computer processors, one or more of the plurality of entities not designated as an entity of interest from the modelled network; and

converting, by the one or more computer processors, the modelled network into a uni-modal network, where the uni-modal network contains a plurality of nodes designated as entities of interest connected by a plurality of resistors designated as simplified weighted links between the entities of interest, where each of the plurality of resistors has an associated resistance representative of a strength of connection between each of the plurality of nodes, with a greater resistance indicating a weaker connection as a resistance between each of the plurality of nodes is an inverse of the weighted value assigned to each of the plurality of entities connected by each of the plurality of links replaced by the plurality of nodes and associated resistance.

2. The method of claim 1, wherein determining the plurality of entities connected by the plurality of links within the multi-modal network, further comprises one or more of:

receiving, by the one or more computer processors, the multi-modal network as a collection of user inputs, where the collection of user inputs includes the plurality of entities connected by the plurality of links;

retrieving, by the one or more computer processors, the multi-modal network from a database; and

monitoring, by the one or more computer processors, one or more real-time interactions and one or more relationships between the plurality of entities, wherein monitoring includes accounting for each of the plurality of connections between each of the plurality of entities within the multi-modal network.

3. The method of claim 1, wherein assigning the weighted value to each of the plurality of links connecting the plurality of entities, further comprises:

assigning, by the one or more computer processors, the weighted value to each of the plurality of links connecting the plurality of entities based, at least in part, on a plurality of semantics associated with a type of connection and a value of relevance associated with the type of connection.

4. The method of claim 1, wherein the modelled network replaces each of the plurality of links connecting the plurality of entities with a plurality of resistors to represent an equivalent electrical circuit.

5. The method of claim 1, wherein converting the multi-modal network into the modelled network, further comprises:

modelling, by the one or more computer processors, each of the plurality of links connecting each of the plurality of entities having a weighted value greater than zero with a resistor;

discarding, by the one or more computer processors, each of the plurality of links having a weighted value of zero; and

determining, by the one or more computer processors, a resistance for each of a plurality of resistors in an equivalent electrical circuit based at least in part, on the weighted value assigned to each of the plurality of links.

6. The method of claim 5, wherein determining the resistance for each of the plurality of resistors, further comprises:

determining, by the one or more compute processors, the resistance of each of the plurality of resistors replacing each of the plurality of links having a weighted value greater than zero as an inverse of the weights assigned to each of the plurality of links; and

reducing, by the one or more computer processors, each of the plurality of resistors in parallel between a pair of nodes to an equivalent single resistor using a standard parallel resistors formula, wherein reducing to the equivalent single resistor is equivalent to adding each of the weighted values of each of the plurality of links in parallel.

7. The method of claim 1, wherein eliminating one or more of the plurality of entities not designated as an entity of interest from the modelled network, further comprises:

determining, by the one or more computer processors, each of a plurality of nodes in the modelled network representative of the plurality of entities that is not of a type of interest for a particular purpose based, at least in part, on user input;

removing, by the one or more computer processors, each of the plurality of nodes one at a time, replacing each of the plurality of nodes with one or more resistors between one or more neighboring nodes that each of the plurality of nodes shares a connection; and

determining, by the one or more computer processors, a resistance for each of the one or more resistors replacing each of the plurality of nodes utilizing a standard node elimination formula for the one or more neighboring nodes.

8. A computer program product for processing a multi-modal network to reduce modality, the computer program product comprising:

one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising;

program instructions to determine a plurality of entities connected by a plurality of links within a multi-modal network;

program instructions to assign a weighted value to each of the plurality of links connecting the plurality of entities;

program instructions to convert the multi-modal network into a modelled network based, at least in part, on the weighted value assigned to each of the plurality of links;

program instructions to eliminate one or more of the plurality of entities not designated as an entity of interest from the modelled network; and

program instructions to convert the modelled network into a uni-modal network, where the uni-modal network contains a plurality of nodes designated as entities of interest connected by a plurality of resistors designated as simplified weighted links between the entities of interest, where each of the plurality of resistors has an associated resistance representative of a strength of connection between each of the plurality of nodes, with a greater resistance indicating a weaker connection as a resistance between each of the plurality of nodes is an inverse of the weighted value assigned to each of the plurality of entities connected by each of the plurality of links replaced by the plurality of nodes and associated resistance.

9. The computer program product of claim 8, wherein program instructions to determine the plurality of entities connected by the plurality of links within the multi-modal network, further comprise one or more of:

program instructions to receive the multi-modal network as a collection of user inputs, where the collection of user inputs includes the plurality of entities connected by the plurality of links;

program instructions to retrieve the multi-modal network from a database; and

program instructions to monitor one or more real-time interactions and one or more relationships between the plurality of entities, wherein monitoring includes accounting for each of the plurality of connections between each of the plurality of entities within the multi-modal network.

10. The computer program product of claim 8, wherein program instructions to assign the weighted value to each of the plurality of links connecting the plurality of entities, further comprise:

program instructions to assign the weighted value to each of the plurality of links connecting the plurality of entities based, at least in part, on a plurality of semantics associated with a type of connection and a value of relevance associated with the type of connection.

11. The computer program product of claim 8, wherein the modelled network replaces each of the plurality of links connecting the plurality of entities with a plurality of resistors to represent an equivalent electrical circuit.

12. The computer program product of claim 8, wherein program instructions to convert the multi-modal network into the modelled network, further comprise:

program instructions to model each of the plurality of links connecting each of the plurality of entities having a weighted value greater than zero with a resistor;

program instructions to discard each of the plurality of links having a weighted value of zero; and

program instructions to determine a resistance for each of a plurality of resistors in an equivalent electrical circuit based at least in part, on the weighted value assigned to each of the plurality of links.

13. The computer program product of claim 12, wherein program instructions to determine the resistance for each of the plurality of resistors, further comprise:

program instructions to determine the resistance of each of the plurality of resistors replacing each of the plurality of links having a weighted value greater than zero as an inverse of the weights assigned to each of the plurality of links; and

program instructions to reduce each of the plurality of resistors in parallel between a pair of nodes to an equivalent single resistor using a standard parallel resistors formula, wherein reducing to the equivalent single resistor is equivalent to adding each of the weighted values of each of the plurality of links in parallel.

14. The computer program product of claim 8, wherein program instructions to eliminate one or more of the plurality of entities not designated as an entity of interest from the modelled network, further comprises:

program instructions to determine each of a plurality of nodes in the modelled network representative of the plurality of entities that is not of a type of interest for a particular purpose based, at least in part, on user input;

program instructions to remove each of the plurality of nodes one at a time, replacing each of the plurality of nodes with one or more resistors between one or more neighboring nodes that each of the plurality of nodes shares a connection; and

program instructions to determine a resistance for each of the one or more resistors replacing each of the plurality of nodes utilizing a standard node elimination formula for the one or more neighboring nodes.

15. A computer system for processing a multi-modal network to reduce modality, the computer system comprising:

one or more computer processors;

one or more computer readable storage media; and

program instructions stored on at least one of the one or more computer readable storage media for execution by at least one of the one or more computer processors, the program instructions comprising;

program instructions to program instructions to determine a plurality of entities connected by a plurality of links within a multi-modal network;

program instructions to assign a weighted value to each of the plurality of links connecting the plurality of entities;

program instructions to convert the multi-modal network into a modelled network based, at least in part, on the weighted value assigned to each of the plurality of links;

program instructions to eliminate one or more of the plurality of entities not designated as an entity of interest from the modelled network; and

program instructions to convert the modelled network into a uni-modal network, where the uni-modal network contains a plurality of nodes designated as entities of interest connected by a plurality of resistors designated as simplified weighted links between the entities of interest, where each of the plurality of resistors has an associated resistance representative of a strength of connection between each of the plurality of nodes, with a greater resistance indicating a weaker connection as a resistance between each of the plurality of nodes is an inverse of the weighted value assigned to each of the plurality of entities connected by each of the plurality of links replaced by the plurality of nodes and associated resistance.

16. The computer system of claim 15, wherein program instructions to determine the plurality of entities connected by the plurality of links within the multi-modal network, further comprise one or more of:

program instructions to receive the multi-modal network as a collection of user inputs, where the collection of user inputs includes the plurality of entities connected by the plurality of links;

program instructions to retrieve the multi-modal network from a database; and

program instructions to monitor one or more real-time interactions and one or more relationships between the plurality of entities, wherein monitoring includes accounting for each of the plurality of connections between each of the plurality of entities within the multi-modal network.

17. The computer system of claim 15, wherein the modelled network replaces each of the plurality of links connecting the plurality of entities with a plurality of resistors to represent an equivalent electrical circuit.

18. The computer system of claim 15, wherein program instructions to convert the multi-modal network into the modelled network, further comprise:

program instructions to model each of the plurality of links connecting each of the plurality of entities having a weighted value greater than zero with a resistor;

program instructions to discard each of the plurality of links having a weighted value of zero; and

program instructions to determine a resistance for each of a plurality of resistors in an equivalent electrical circuit based at least in part, on the weighted value assigned to each of the plurality of links.

19. The computer system of claim 18, wherein program instructions to determine the resistance for each of the plurality of resistors, further comprise:

program instructions to determine the resistance of each of the plurality of resistors replacing each of the plurality of links having a weighted value greater than zero as an inverse of the weights assigned to each of the plurality of links; and

program instructions to reduce each of the plurality of resistors in parallel between a pair of nodes to an equivalent single resistor using a standard parallel resistors formula, wherein reducing to the equivalent single resistor is equivalent to adding each of the weighted values of each of the plurality of links in parallel.

20. The computer system of claim 15, wherein program instructions to eliminate one or more of the plurality of entities not designated as an entity of interest from the modelled network, further comprises:

program instructions to determine each of a plurality of nodes in the modelled network representative of the plurality of entities that is not of a type of interest for a particular purpose based, at least in part, on user input;

program instructions to remove each of the plurality of nodes one at a time, replacing each of the plurality of nodes with one or more resistors between one or more neighboring nodes that each of the plurality of nodes shares a connection; and

program instructions to determine a resistance for each of the one or more resistors replacing each of the plurality of nodes utilizing a standard node elimination formula for the one or more neighboring nodes.