Node relevance determination in an evolving network

Methods and systems for determining a time dependent relevancy score of an agent node among an evolving heterogeneous network are described. A processor may expand the heterogeneous network by generating temporal heterogeneous networks representing states of the heterogeneous network at different times. The processor may extract a set of agent nodes from each temporal heterogeneous network and may generate a relationship network based on the extracted agent nodes for each temporal heterogeneous network. The processor may remove the agent node from the temporal heterogeneous network to generate a conditional relationship network excluding the removed agent node. The processor may determine a relevancy score for the agent node based on the corresponding relationship network and the conditional relationship network. Each relevancy score for the agent node may correspond to a temporal heterogeneous network and may indicate an impact of removing the agent node from the corresponding temporal heterogeneous network.

FIELD

The present application relates generally to computers, and computer applications, and more particularly to computer-implemented methods and systems relating to network analysis.

BACKGROUND

Network analysis systems may be implemented to determine scores of nodes within a network, where the determined scores may indicate an importance of each node with respect to the network. Determination of the scores of the nodes in the network, when the network is static, may provide information on an importance of each node at a particular state of the network at a particular time. However, the network may experience changes, such as additions and removal of nodes and edges, over time. When the changes to the network are neglected, the importance indicated by the determined scores of each node may be inaccurate.

SUMMARY

In some examples, a method for generating relevancy data of at least one node in a heterogeneous network that changes with time is generally described. The method may include generating, by a processor, a series of temporal heterogeneous networks. Each temporal heterogeneous network may be a state of the heterogeneous network at a time window, and each temporal heterogeneous network may include a respective set of agent nodes and a respective set of non-agent nodes. The method may further include, for each temporal heterogeneous network, extracting, by the processor, a set of agent nodes. The method may further include, for each temporal heterogeneous network, generating, by the processor, a relationship network based on the extracted agent nodes. The relationship network may include the extracted agent nodes, and the relationship network corresponds to the temporal heterogeneous network. The method may include, for each agent node among each pair of temporal heterogeneous network and relationship network, removing, by the processor, the agent node from the temporal heterogeneous network. The method may include, for each agent node among each pair of temporal heterogeneous network and relationship network, generating, by the processor, a conditional relationship network based on the remaining agent nodes among the temporal heterogeneous network after the removal of the agent node. The method may include, for each agent node among each pair of temporal heterogeneous network and relationship network, determining, by the processor, a relevancy score for the removed agent node based on the relationship network and based on the conditional relationship network. The relevancy score may correspond to the time window. The method may include generating, by the processor, the relevancy data based on the relevancy scores for each agent node among each temporal heterogeneous network. The relevancy data may indicate changes of the relevancy scores of each agent node with respect to time.

In some examples, a system effective to generate relevancy data for at least one node among a heterogeneous network that changes with time is generally described. The system may include a memory configured to store a database including records related to at least one entity. The system may further include a processor configured to be in communication with the memory. The processor may be configured to generate a series of temporal heterogeneous networks based on the database stored in the memory. Each temporal heterogeneous network may be a state of the heterogeneous network at a time window, and each temporal heterogeneous network includes a respective set of agent nodes and a respective set of non-agent nodes. The processor may be further configured to, for each temporal heterogeneous network, extract a set of agent nodes. The processor may be further configured to, for each temporal heterogeneous network, generate a relationship network based on the extracted agent nodes. The relationship network may include the extracted agent nodes, and the relationship network may correspond to the temporal heterogeneous network. The processor may be further configured to, for each agent node among each pair of temporal heterogeneous network and relationship network, remove the agent node from the temporal heterogeneous network. The processor may be further configured to, for each agent node among each pair of temporal heterogeneous network and relationship network, generate a conditional relationship network based on the remaining agent nodes among the temporal heterogeneous network after the removal of the agent node. The processor may be further configured to, for each agent node among each pair of temporal heterogeneous network and relationship network, determine a relevancy score for the removed agent node based on the relationship network and based on the conditional relationship network. The relevancy score may correspond to the time window. The processor may be further configured to generate the relevancy data based on the relevancy scores for each agent node among each temporal heterogeneous network. The relevancy data may indicate changes of the relevancy scores of each agent node with respect to time.

In some examples, a computer program product for generating relevancy data that represents an importance of a node among a heterogeneous network that changes with time is generally described. The computer program product may include a computer readable storage medium having program instructions embodied therewith. The program instructions may be executable by a processing element of a device to cause the device to perform one or more methods described herein.

DETAILED DESCRIPTION

A system in accordance with the present disclosure (e.g., system100shown inFIG. 1) may determine the importance of one or more nodes with respect to a heterogeneous network that evolves with time. A heterogeneous network may be a network that includes a set of agent nodes and a set of non-agent nodes, and may also include edges representing relationship among the agent nodes and the non-agent nodes. In some examples, a network may be deemed as a heterogeneous network because the agent nodes have possible relationships to one or more specific types of non-agent nodes. An agent node may be a node that creates new components (nodes or edges) in the heterogeneous network. A non-agent node may be a node that does not create new components in the heterogeneous network. An agent node may act as nucleators of network growth and connectivity of the heterogeneous network because of the capability to create new components. Therefore, a determination of a relevancy score for the agent nodes may facilitate identification of the most important nodes among the heterogeneous network. Further, determination of a time dependent relevancy score of an agent node may facilitate a determination of changes to the importance of the agent node, which may further indicate an impact of the agent node may have on the heterogeneous network.

The system100may be implemented to determine time dependent relevancy scores of agent nodes of a heterogeneous network that changes with time. The system100may provide a practical application that improves a network analysis system by addressing challenges of identifying important nodes among a dynamically evolving heterogeneous network. The system100may consider the effects of changes in the heterogeneous network (e.g., addition and removal of nodes and relationships at different times) in the determination of the time dependent relevancy scores of the agent nodes. The system100may provide a structure to consider the impact of nodes in the growth and connectivity of a network and network dynamics.

In an example, a heterogeneous network may include at least one agent, where each agent may be a node representative of an entity such as a person, an organization, and/or another type of entity. Each agent node among the heterogeneous network may have relationships to other agent nodes and non-agent nodes, where the relationships may be represented as an edge, and each edge may connect two nodes. A non-agent node may be a node representative of non-entities, such as a project, a location, a hobby, etc. For each time instance, the system100may generate relationship networks that may include agents, and exclude non-agents, from the heterogeneous network in order to determine a score for each agent in the heterogeneous network at the time instance. The system100may iteratively remove agent nodes from the heterogeneous network, and reconstruct another relationship network based on the remaining agent nodes. The system100may use the relationship network that includes the removed agent node, and the reconstructed relationship network without the removed agent node, to determine a score associated with the heterogeneous network without the removed agent. In some examples, the score may indicate a number of disconnected subcomponents and/or nodes among the heterogeneous network without the removed agent. As such, the score may indicate an importance of the removed agent node with respect to the heterogeneous network by showing an impact of the removal of the removed agent node.

FIG. 1illustrates an example computer system100that can be utilized to implement node relevance determination in an evolving network, arranged in accordance with at least some embodiments described herein. In some examples, the system100may be implemented by a computer device. The system100may include a processor120, a memory122, a network generation module130, and/or a relevancy score module150. The processor120, the memory122, the network generation module130, and the relevancy score module150may be configured to be in communication with each other. The processor120may be a central processing unit of a computer device implementing the system100. In some examples, the processor120may be configured to control operations of the network generation module130and the relevancy score module150. In some examples, the network generation module130and the relevancy score module150may be hardware components such as programmable logic devices, microcontrollers, memory devices, and/or other hardware components, of the processor120. In some examples, the network generation module130and the relevancy score module150may be software modules that may be implemented with the processor120to perform one or more tasks. In some examples, the network generation module130and the relevancy score module150may be packaged as an application that may be executed by the processor120in order to implement the system100. In some examples, one or more of the processor120, the memory122, the network generation module130, and the relevancy score module150may be parts of resources provided by a cloud computing platform.

The memory122may be configured to selectively store instructions executable by the processor120, the network generation module130, and the relevancy score module150. For example, in one embodiment, the memory122may store a set of relevancy instructions124, where the relevancy instructions124may include instructions, such as executable code, related to graph and network algorithms, node ranking algorithms, network visualization algorithms, and/or other algorithms related to graphs and networks. The processor120, the network generation module130, and the relevancy score module150may each be configured to execute one or more portions of the relevancy instructions124in order to facilitate implementation of the system100.

The memory122may be further configured to store a relational database126. The relational database126may include datasets indicating relationships among entities of a network. For example, the relationship database126may include records, where each record may correspond to an entity. Each record may include one or more attributes, and two or more entities may be deemed as related if their records share one or more attributes. For example, in a relational database for a social media network, each record may correspond to a person, and attributes may include a location, a job, a hobby, an organization, and/or other attributes. In an example, when two records of the relational database for the social media network shares a same organization attribute, then the relational database may indicate a relationship, such as “coworkers”, exists between the entities of the two records. The relational database126may further include a set of time indices, where each time index may be a timestamp of additions and removals of entities and/or attributes to the relational database126, or may be a timestamp of relationships being formed and removed from the relational database126. The relational database126may further include indications of whether a particular entity created one or more other entities, and/or relationships with other entities or non-entities, among the relational database126.

The memory122may be further configured to store a node database128. The node database128may be a database including entries that indicate whether each node among the relational database126is an agent node or a non-agent node. In an example shown inFIG. 1, the node database128may indicate that the nodes141,142,144are agent nodes, and the nodes143,145are non-agent nodes. In an example embodiment, the node database128may be a part of the relational database126.

The processor120may be configured to retrieve, or receive, datasets from one or more sources, and may update the relational database126and the node database128using the datasets retrieved from the sources. In some examples, the sources may include storage devices that may be resources provided by a cloud computing platform. In an example, a user of a social media network may update a job to indicate a job change. The processor120may receive the job change information and may update the relational database126to indicate the job change. The update of the job attribute performed by the user may facilitate a creation of one or more a new relationships in the relational database126(e.g., addition of new coworkers). Thus, the processor120may determine that a node representing the user that changed job may be an agent node because new relationships are facilitated by the node representing the user. The processor120may be further configured to register the times in which entities entered and leave the relational database, and the times in which relationships are formed and removed from the relational database126. The processor120may be further configured to determine whether a node is an agent or a non-agent, and update the node database128accordingly.

The network generation module130may expand a heterogeneous network into a series of temporal heterogeneous networks132based on the relational database126. Each temporal heterogeneous network132may include a respective set of agent nodes, non-agent nodes, and edges. Each temporal heterogeneous network132may correspond to a time window. The network generation module130may use the records and time indices indicated by the relational database126to generate the temporal heterogeneous networks132. For example, the network generation module130may extract records associated with a time window T from the relational database126to generate a temporal heterogeneous network132for the time window T. Each temporal heterogeneous network132may be a state of the heterogeneous network at a time window, where the time window may be a time in the past.

In some examples, the processor120may be configured to anonymize the records in relational database prior to generating the temporal heterogeneous networks132, where generation of the temporal heterogeneous networks132may be based on the anonymized records.

In an example, the heterogeneous network at a current time may be in a current state. The system100may receive a request to rank a set of agent nodes in a time period that spans from one year ago up to half a year ago. The network generation module130may generate a number of temporal heterogeneous networks132based on the request and based on time intervals that may be specified by the relevancy instructions124. For example, the network generation module130may generate three temporal heterogeneous networks at two-month intervals, or may generate six temporal heterogeneous networks at one-month intervals, where the current state of the heterogeneous network may not be among the generated temporal heterogeneous network based on the time period requested.

In another example, a user may be assigned to a plurality of projects at different times. The assignments of the projects to the user may change over time. Thus, a set of temporal heterogeneous networks may provide indications of the assignment time of each project, the completion time of each project, the duration of time to work on each project, a number of projects assigned to the user at each time window, and/or other attributes relating to the project assignments of the user.

The network generation module130may generate the temporal heterogeneous networks132at time intervals that may be specified by relevancy instructions124, or at time intervals that may be defined by a user of the system100. For example, the network generation module130may generate twelve temporal heterogeneous networks132, one for each month, in order for the system100to determine relevancy scores of agent nodes within a one year time span.

In an example shown inFIG. 1, the temporal heterogeneous network132at time T may include agent nodes141,142,144and non-agent node134. The network generation module130may generate additional temporal heterogeneous networks132that correspond to different time windows. By expanding the heterogeneous network into discrete time series of networks, an evolution of agent nodes going in or out of the heterogeneous network, as well as the relationship dynamics over time, may be revealed.

Upon generating a series of temporal heterogeneous networks132, the network generation module130may generate a series of relationship networks134, where each relationship network134corresponds to a temporal heterogeneous network132. In the example shown inFIG. 1, the network generation module130may extract agent nodes141,142,144from the temporal heterogeneous network132at time T, and may infer relationships among the extracted agent nodes141,142,144. The network generation module130may infer relationships among agent nodes141,142,144based on the connections of the agent nodes141,142,144to non-agent node134in the temporal heterogeneous network132at time T. The network generation module130may generate a relationship network134that corresponds to the temporal heterogeneous network132at time T, based on the extracted agent nodes141,142,144and based on the relationships inferred among agent nodes141,142,144. As a result, the relationship network134may include agent nodes141,142,144and the inferred relationships, and excludes non-agent node143. Each inferred relationship (edge) indicated by the relationship network134may represent a potential presence of a past relationship between the two entities (nodes) connected by the inferred relationship. A plurality of pairs including a temporal heterogeneous network132and a relationship network134may be generated by network generation module130.

The network generation module130may further generate a series of conditional relationship networks136, where each conditional relationship network136may be associated with an agent node and may be generated based on a corresponding pair of temporal heterogeneous network132and relationship network134. The network generation module130may iteratively remove agent nodes from the temporal heterogeneous network132and construct a corresponding conditional relationship network136based on the agent nodes remaining at the temporal heterogeneous network132. In some examples, the network generation module130may generate a copy of the temporal heterogeneous network132, and remove agent nodes from the copy such that the original temporal heterogeneous network132may remain intact. In the example shown atFIG. 1, the network generation module130may remove agent node141from the temporal heterogeneous network132at time T. The network generation module130may further identify nodes and edges that may have been created by agent node141, and remove the identified nodes and edges from the temporal heterogeneous network132. In the example shown inFIG. 1, the network generation module130may determine that non-agent node143was created by agent node141and may remove non-agent node143from the temporal heterogeneous network132. The network generation module130may further remove any edges that was connected to the removed agent node141and removed non-agent node143. The network generation module130may generate a conditional relationship network136based on the remaining agent nodes142,144, and may infer relationships between agent nodes142,144. In the example ofFIG. 1, the network generation module130may determine that upon removing the agent node141, the non-agent node143, and corresponding edges, there is no relationship between agent nodes142,144.

The conditional relationship network136may include one or more subcomponents that may be parts of the temporal heterogeneous network132, where the one or more subcomponents may be disconnected from each other. A subcomponent of a network may be a group of one or more components (nodes and edges connecting the nodes) that are disconnected from other parts of the network. Each subcomponent of the conditional relationship network136may include one or more agent nodes that remained from a removal of a particular agent node and/or relationships inferred by network generation module130. In the example shown inFIG. 1, conditional relationship network136may include the agent nodes142as a first subcomponent, and may include the agent node144as a second subcomponent, which may indicate that agent nodes142,144are no longer related upon the removal of agent node141.

The relevancy score module150may be configured to determine a score for the agent node141at time T based on the conditional relationship network136at time T without agent node141. In an example, the relevancy score module150may compare a number of subcomponents in the relationship network134(“1”) with a number of subcomponents in the conditional relationship network136without agent node141(“2”). Based on the comparison, the relevancy score module150may determine that the number of subcomponents increased by “1”, and may assign a score of “1” to node141at time T. In some examples, an increase in a number of subcomponents may increase an importance of the removed agent node because an increase in the number of subcomponents may indicate entities are being disconnected from the network without the removed agent node (removing the agent node creates disconnected entities).

In some examples, the relevancy score module150may determine a relevancy score of a node by using other techniques, such as using the number of subcomponents in conditional relationship network136without the removed node, determining a number of connected nodes and/or edges in conditional relationship network136, and/or other parameters of conditional relationship network136. In some examples, the relevancy score module150may be configure to apply other node scoring techniques to determine the relevancy scores of the agent nodes.

Upon determining relevancy score for each agent node among each temporal heterogeneous network132at each time window, the relevancy score module150may generate relevancy data152. The relevancy data152may include the determined scores for each agent node among each temporal heterogeneous network132at each time window. In some examples, the relevancy score module150may include a ranking of the agent nodes based on the scores among the relevancy data152. For example, the relevancy data152may include a ranking of agents nodes based on sorting the relevancy scores for the agent nodes in an increasing or a decreasing order at each time window. In another example, the relevancy data152may include a ranking of the agent nodes based on averages of the relevancy scores across a set of time windows. For example, the relevancy data152may include ranked scores that are averages of relevancy scores for each node within a time span of one year. In another example, the relevancy data152may include a ranking of the agent nodes based on an amount of time in which the relevancy scores remains above a threshold. For example, a first node may be ranked higher than a second node if a first relevancy score of the first node remains above a threshold for six months while a second relevancy score of the second node remains above the threshold for three months. The relevancy data152may include rankings of the agent nodes based on various parameters associated with the determined relevancy scores, and based on a desired implementation of the system100.

FIGS. 2A, 2B, 2C, 2Dillustrate the example system ofFIG. 1with additional details relating to a temporal heterogeneous network202, a relationship network204, a conditional relationship network206, and a condition relationship network208, respectively, arranged in accordance with at least some embodiments described herein.FIGS. 2A, 2B, 2C, 2Dmay be described below with references to the above descriptions ofFIG. 1.

FIGS. 2A, 2B, 2C, 2Dmay be related to an example where the system100ofFIG. 1may be implemented to analyze allocation of machine hosting services. The temporal heterogeneous network202, shown inFIG. 2A, may be a dynamic heterogeneous network representing one or more machines hosting one or more services. The temporal heterogeneous network202may include agent nodes210,211,212,213,214, where each agent node may represent a machine. The temporal heterogeneous network202may further include non-agent nodes220,222, where each non-agent node may represent a service. Agent nodes211,212may be connected to non-agent node220, which may indicate that machines represented by agent nodes211,212are hosting a service represented by non-agent node220. Similarly, agent nodes213,214may be connected to non-agent node222, which may indicate that machines represented by agent nodes213,214are hosting a service represented by non-agent node222. Agent node210may be connected to non-agent nodes220,222, which may indicate that a machine represented by agent node210may be hosting services represented by non-agent node220,222.

The network generation module130of the system100may extract agent nodes210,211,212,213,214from the temporal heterogeneous network202. The network generation module130may determine relationships among the extracted agent nodes210,211,212,213,214, based on the non-agent nodes220,222of the temporal heterogeneous network202. For example, the network generation module130may determine that agent nodes210,211,212are connected to a common non-agent node220and, in response, may infer relationships (represented by edges230) among agent nodes210,211,212. The inferred relationships may indicate that agent nodes210,211,212include at least one similarity, which is this example, is commonly hosting a same service represented by non-agent node220. Similarly, the network generation module130may determine that agent nodes210,213,214are connected to a common non-agent node222and, in response, may infer relationships (represented by edges231) among agent nodes210,213,214. The network generation module130may generate the relationship network204, shown inFIG. 2B, based on the extracted agent nodes210,211,212,213,214, and based on the inferred relationships represented by edges230,231.

The network generation module130may iteratively remove one or more of agent nodes210,211,212,213,214from the temporal heterogeneous network202, and generate a conditional relationship network (such as206,208) upon each removal of one or more agent nodes. In an example, the network generation module130may remove the agent node210from the temporal heterogeneous network202and may generate a conditional relationship network206based on the remaining agent nodes211,212,213,214. Upon removing agent node210, agent nodes211,212remain connected to non-agent node220and the network generation module130may infer a relationship between agent nodes211,212. Similarly, agent nodes213,214remain connected to non-agent node222and the network generation module130may infer a relationship between agent nodes213,214. The network generation module130may generate the conditional relationship network206, shown inFIG. 2C, where agent nodes211,212are connected by a first inferred edge, and agent nodes213,214are connected by a second inferred edge. The conditional relationship network206without the remove agent node210may include a first subcomponent240and a second subcomponent241.

Subsequently, the network generation module130may remove the agent node211from the temporal heterogeneous network202and may generate a conditional relationship network208based on the remaining agent nodes210,212,213,214. Upon removing agent node211, agent nodes210,212remain connected to non-agent node220and the network generation module130may infer a relationship between agent nodes210,212. Similarly, agent nodes210,213,214remain connected to non-agent node222and the network generation module130may infer relationships between agent nodes210,213,214. The network generation module130may generate the conditional relationship network208, shown inFIG. 2D, where agent nodes210,212are connected by an inferred edge and agent nodes210,213,214are connected by a set of inferred edges. The conditional relationship network208without the remove agent node211may include one subcomponent (as indicated by the dotted circle).

The network generation module130may continue to iteratively remove the remaining agent nodes212,213,214in order to generate further conditional relationship networks. When the network generation module130completes generation of conditional relationship networks for all agent nodes, the network generation module130may analyze another temporal heterogeneous network at a new time window, and repeat the generation of relationship networks, removal of agent nodes, and generation of conditional relationship networks for the new time window.

The relevancy score module150may compare the conditional relationship network206with the relationship network204to determine a relevancy score for the agent node210that was removed to generate the conditional relationship network206. The relevancy score module150may determine that relationship network204includes one subcomponent, and conditional relationship network206includes two subcomponents. The relevancy score module150may assign a score of “1” to agent node210to indicate that the number of subcomponents has increased by “1”.

Similarly, the relevancy score module150may compare the conditional relationship network208with the relationship network204to determine a relevancy score for the agent node211that was removed to generate the conditional relationship network208. The relevancy score module150may determine that relationship network204includes one subcomponent, and conditional relationship network208also includes one subcomponent. The relevancy score module150may assign a score of “0” to agent node211to indicate that the number of subcomponents has not changed. The relevancy score module150may determine time dependent relevancy scores for all agent nodes (e.g., relevancy scores of each agent node at more than one time window).

The relevancy score module150may rank the agent node210higher than the agent node211in response to agent node210having a high relevancy score. The higher rank of agent node210relative to agent node211may indicate that agent node210may be more important than the agent node211. Since the example relating toFIGS. 2A, 2B, 2C, 2Drelates to allocation of machines configured to host services, the higher rank of210may indicate that removal of a machine represented by agent node210from the network of machines represented by agent nodes210,211,212,213,214, may have a greater impact than a removal of a machine represented by agent node211. If the relevancy score of agent node210is a highest score among relevancy scores for all agent nodes210,211,212,213,214, then the machine represented by the agent node210may be identified as a most important node among the network of machines, and the system100may recommend to retain the machine represented by the agent node210.

The system100may be implemented to extract a set of machines hosting services and infer their relationships (edges) by common association with a specific kind of service in a dynamic heterogeneous network representing the machines and services hosted by the machines. The system100may derive a times series of relevance scores and rank the machines based on their robustness. As such, the system100may be implemented as a resource allocation system enhanced with techniques described by the present disclosure. Thus, in some aspects, the system of the present disclosure may provide improvements in computer or machine resource allocation and efficiency in computer network or computer architecture over time. In some aspects, an automated or autonomous system may be provided that can automatically or autonomously change or adjust the allocation of machine resources in a network of computer systems, based on receiving a signal representing scores or importance associated with the machines in the computer network (e.g., turn off (deactivate) a machine or turn on (activate) a machine in a network). For instance, such signals may automatically cause one or more machines to be reallocated.

In some examples, the network generation module130may remove more than one agent node and may generate conditional relationship networks based on removal of more than one agent nodes. A number of agent nodes to be removed may be defined by the relevancy instructions stored in the memory122, and may be based on a desired implementation of system100.

FIG. 3illustrates the example system ofFIG. 1with additional details relating to node relevance determination in an evolving network, arranged in accordance with at least some embodiments described herein.FIG. 3may include references to components of the computer system100ofFIG. 1, and may be described below with references to the above descriptions ofFIG. 1.

In an example shown inFIG. 3, the network generation module130may generate a series of temporal heterogeneous networks132, a series of relationship networks135, and a series of conditional relationship network136. Each temporal heterogeneous network132and each relationship network134may correspond to a time window, and each conditional relationship network136may correspond to a time window and a removed agent node.

As shown by the example inFIG. 3, each time window, including time301,302,303,310, may correspond to a temporal heterogeneous network, a relationship network, and one or more conditional relationship network136. The temporal heterogeneous network132at time301may include different sets of nodes from the temporal heterogeneous network132at times302,303, and310. The temporal heterogeneous networks132may be different at different times due to additions and removals of nodes and edges as time changes. Thus, the series of relationship networks134generated from the network generation module130may be different from each other.

At each time, the network generation module130may iteratively remove agent nodes from the temporal heterogeneous networks132in order to generate the series of conditional relationship networks136.

The system100may be implemented as a network analysis system to perform network analysis on resource allocations. In an example, an agent node may represent a train track and a non-agent node may represent a train station. An implementation of the system100may provide analysis on an impact of removing a particular train track. A transit authority may use the results from the analysis to make decisions such as update train infrastructures, schedule maintenance of train tracks, determining whether to remove a train track that may not be as busy as other train tracks, and/or other decisions.

FIG. 4illustrates a flow diagram relating to node relevance determination in an evolving network, arranged in accordance with at least some embodiments presented herein. The process inFIG. 4may be implemented using, for example, computer system100discussed above. An example process may include one or more operations, actions, or functions as illustrated by one or more of blocks402,404,406,408,410,412, and/or414. Although illustrated as discrete blocks, various blocks may be divided into additional blocks, combined into fewer blocks, eliminated, or performed in parallel, depending on the desired implementation.

Processing may begin at block402, where a processor may expand a heterogeneous network by generating a series of temporal heterogeneous networks denoted as A1, A2, . . . , AN.

Processing may continue from block402to blocks404(including404a,404b). At block404a, the processor may extract a set of agent nodes from the temporal heterogeneous network A1. At block404b, the processor may extract a set of agent nodes from the temporal heterogeneous network A2. The processor may further extract agent nodes from each temporal heterogeneous network up to AN.

Processing may continue from blocks404to blocks406(including406a,406b). At block406a, the processor may generate a relationship network, denoted as B1, based on the agent nodes extracted from the temporal heterogeneous network A1. At block406b, the processor may generate a relationship network, denoted as B2, based on the agent nodes extracted from the temporal heterogeneous network A2. The processor may further generate a series of relationship networks up to BN, based on the agent nodes extracted from a corresponding temporal heterogeneous network. A number of relationship networks may be equivalent to a number of temporal heterogeneous networks.

Processing may continue from blocks406to blocks408(including408a,408b,408c,408d). At block408a, the processor may remove a first agent node, denoted as X1, from the temporal heterogeneous network A1. At block408b, the processor may remove a second agent node, denoted as X2, from the temporal heterogeneous network A1. At block408c, the processor may remove the first agent node X1from the temporal heterogeneous network A2. At block408d, the processor may remove the second agent node X2from the temporal heterogeneous network A2. In some examples, the processor may remove more than one agent node at blocks408.

Processing may continue from blocks408to blocks410(including410a,410b,410c,410d). At block410a, the processor may generate a conditional relationship network C1based on agent nodes that remained at the temporal heterogeneous network A1after the removal of agent node X1, where the conditional relationship network C1excludes the removed agent node X1. At block410b, the processor may generate a conditional relationship network C2based on agent nodes that remained at the temporal heterogeneous network A1after the removal of agent node X2, where the conditional relationship network C2excludes the removed agent node X2. At block410c, the processor may generate a conditional relationship network D1based on agent nodes that remained at the temporal heterogeneous network A2after the removal of agent node X1, where the conditional relationship network D1excludes the removed agent node X1. At block410d, the processor may generate a conditional relationship network D2based on agent nodes that remained at the temporal heterogeneous network A2after the removal of agent node X2, where the conditional relationship network D2excludes the removed agent node X2.

Processing may continue from blocks410to blocks412(including412a,412b,412c,412d). At block412a, the processor may determine a relevancy score S1for the agent node X1based on the relationship network B1and the conditional relationship network C1. At block412b, the processor may determine a relevancy score T1for the agent node X2based on the relationship network B1and the conditional relationship network C2. At block412c, the processor may determine a relevancy score S2for the agent node X1based on the relationship network B2and the conditional relationship network D1. At block412d, the processor may determine a relevancy score T2for the agent node X2based on the relationship network B2and the conditional relationship network D2.

Processing may continue from blocks412to block414. At block414, the processor may generate relevancy data based on the relevancy scores S1, T1, S2, T2, where the relevancy data may be analyzed by the processor to determine an importance of agent nodes X1, X2with respect to the heterogeneous network.

FIG. 5illustrates an example result from an implementation of the example system ofFIG. 1in one embodiment of the present disclosure.FIG. 5may include references to components of the computer system100ofFIG. 1, and may be described below with references to the above descriptions ofFIG. 1.

Generation of the relevancy data152by the relevancy score module150may include generation of various analysis objects, such as reports, charts, graphs, and/or other objects. In an example shown inFIG. 5, a graph500may be generated by the relevancy score module150, and may be a part of relevancy data152. The graph500may include one or more plots, where each plot may show a change in a relevancy score of an agent node over time.

The graph500may provide information such as temporal changes to the heterogeneous network. As the heterogeneous network evolves with time, a number of agent nodes in the heterogeneous network may change. For example, the graph500may indicate that at a time511, the heterogeneous network may include at least one agent node501. As time progresses, at time512, the heterogeneous network may include at least two agent nodes501,502. The graph500may also provide an indication that the agent node502was added to the heterogeneous network at a time between the times511and512.

The graph500may also provide indications on changes of a ranking of the agent nodes at different times. For example, at time512, the agent node502may be ranked higher than the agent node501due to the agent node502having a relevancy score that is greater than a relevancy score of the agent node501. As time progresses, such as at a time513, the agent node501may have a relevancy score that is greater than a relevancy score of the agent node502and thus, the agent node501may be ranked higher than the agent node502at the time513.

At a time514, the graph500may indicate that the heterogeneous network may include five agent nodes501,502,503,504,505, and may provide an indication of a ranking of the five agent nodes. The ranking of the five agent nodes, at time514, may be based on a decreasing order of the relevancy scores, such that the agent node501may be ranked highest (most important) and the agent node505may be ranked lowest (least important). In some examples, the system100may output analysis objects, such as the graph500, on a user interface that may be displayed by the system100on a display device. A user of the system100may view the outputted analysis objects in order to make decisions on applications such as adjusting resource allocations. In another example, a user of the system100may view the outputted analysis objects in order to make adjustments to an implementation of system100, such as requesting analysis of agent nodes across a new time span, define a new number of agent nodes to analyze, and/or other requests.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

FIG. 8depicts abstraction model layers according to an embodiment of the present invention. Referring now toFIG. 8, a set of functional abstraction layers provided by cloud computing environment50(FIG. 7) is shown. It should be understood in advance that the components, layers, and functions shown inFIG. 8are intended to be illustrative only and embodiments of the invention are not limited thereto. As depicted, the following layers and corresponding functions are provided: