Method and device for generating temporal graph with time-bound communities

1 . A method for generating a temporal graph with time-bound communities, comprising:

grouping a set of nodes in a target scenario to obtain nodes included in each of a plurality of time-bound communities, wherein the time-bound community represents a community that is in active status for a period of time and eventually goes extinct; and numbers of nodes included in the plurality of time-bound communities follow a power-law distribution;

generating a time window for each of the plurality of time-bound communities, wherein starting times of the time windows corresponding to the plurality of time-bound communities follow a uniform distribution, and lengths of the time windows corresponding to the plurality of time-bound communities follow a power-law distribution, wherein generating the time window for each of the plurality of time-bound communities comprises:

determining an expectation of a length of a time window of a first time-bound community based on a number of nodes included in the first time-bound community;

determining a probability density function of the length of the time window of the first time-bound community based on the expectation of the length of the time window of the first time-bound community;

obtaining a length of a target time window of the first time-bound community by sampling the probability density function of the length of the time window of the first time-bound community;

obtaining a starting time of the target time window of the first time-bound community by sampling based on the length of the target time window of the first time-bound community and a preset time range; and

determining the target time window of the first time-bound community based on the starting time of the target time window of the first time-bound community and the length of the target time window of the first time-bound community;

constructing an index structure that is transferable between different time-bound communities, and generating, based on the nodes included in respective time-bound communities, the time windows of respective time-bound communities, and the index structure, temporal edges within each of the plurality of time-bound communities and/or temporal edges between the different time-bound communities of the plurality of time-bound communities; and

generating the temporal graph of the target scenario based on the nodes included in each of the plurality of time-bound communities, the time window of each of the plurality of time-bound communities, and the temporal edges within each of the plurality of time-bound communities and/or the temporal edges between the different time-bound communities of the plurality of time-bound communities.

2 . The method according to claim 1 , wherein constructing the index structure that is transferable between the different time-bound communities comprises:

selecting a time-bound community containing a largest number of nodes from the plurality of time-bound communities, and establishing an index of out-degree distribution and an index of in-degree distribution for the time-bound community containing the largest number of nodes; and

selecting a time-bound community with a longest time window from the plurality of time-bound communities, and establishing an index of timestamp distribution for the time-bound community with the longest time window.

3 . The method according to claim 2 , wherein generating, based on the nodes included in the respective time-bound communities, the time windows of the respective time-bound communities, and the index structure, the temporal edges within each of the plurality of time-bound communities and/or the temporal edges between the different time-bound communities of the plurality of time-bound communities comprises:

generating a tree structure with respect to nodes included in a second first time-bound community, wherein the second first time-bound community is any of the plurality of time-bound communities;

determining an out-degree of a first source node based on the index of out-degree distribution, wherein the first source node is any source node in the tree structure;

selecting a first target node corresponding to the first source node from the nodes included in the second first time-bound community based on the index of in-degree distribution, wherein a number of the first target nodes is same as the out-degree of the first source node;

generating, based on the index of timestamp distribution, a timestamp corresponding to the first target node from a time window of the second first time-bound community; and

generating a temporal edge within the second first time-bound community associated with the first source node based on the first source node, the first target node, and the timestamp corresponding to the first target node.

4 . The method according to claim 3 , wherein generating, based on the nodes included in the respective time-bound communities, the time windows of the respective time-bound communities, and the index structure, the temporal edges within each of the plurality of time-bound communities and/or the temporal edges between the different time-bound communities of the plurality of time-bound communities further comprises:

determining a between-out-degree of the first source node, wherein the between-out-degree represents a number of edges associated with the node that do not belong to any of the time-bound communities;

selecting a second target node corresponding to the first source node from the nodes included in the plurality of time-bound communities based on the index of in-degree distribution, wherein a number of second target nodes is the same as the between-out-degree of the first source node, and the first source node and the second target node belong to different time-bound communities;

generating, based on the index of timestamp distribution, a timestamp corresponding to the second target node from a complementary set of a common portion of a time window of a time-bound community where the first source node is located and a time window of a time-bound community where the second target node is located; and

generating a temporal edge between the different time-bound communities associated with the first source node based on the first source node, the second target node, and the timestamp corresponding to the second target node.

5 . The method according to claim 4 , wherein a number of the temporal edges between the different time-bound communities of the plurality of time-bound communities is determined by a preset messing parameter, wherein the messing parameter represents a degree of clarity of a boundary between the different time-bound communities.

6 . The method according to claim 1 , wherein determining the expectation of the length of the time window of the first time-bound community based on the number of the nodes included in the first time-bound community comprises:

calculating an average value of the length of the time window of the first time-bound community based on the number of the nodes included in the first time-bound community, wherein a logarithmic correlation exists between the average value of the length of the time window of the first time-bound community and the number of the nodes included in the first time-bound community; and

determining the average value of the length of the time window of the first time-bound community as the expectation of the length of the time window of the first time-bound community.

7 . The method according to claim 1 , wherein the plurality of time-bound communities comprise a preset number of overlapping structures, wherein each of the overlapping structures comprises a shared node present in two time-bound communities; and a degree of the shared node exceeds degrees of other nodes in either of the two time-bound communities, and a ratio of a number of shared nodes to a number of nodes in either of the two time-bound communities is a preset value.

8 . One or more non-transitory computer readable storage medium storing computer program instructions, which, when executed by a processor, cause the processor to:

group a set of nodes in a target scenario to obtain nodes included in each of a plurality of time-bound communities, wherein the time-bound community represents a community that is in active status for a period of time and eventually goes extinct; and numbers of nodes included in the plurality of time-bound communities follow a power-law distribution;

generate a time window for each of the plurality of time-bound communities, wherein starting times of the time windows corresponding to the plurality of time-bound communities follow a uniform distribution, and lengths of the time windows corresponding to the plurality of time-bound communities follow a power-law distribution, wherein the processor being configured to generate the time window for each of the plurality of time-bound communities comprises the processor being configured to:

determine an expectation of a length of a time window of a first time-bound community based on a number of nodes included in the first time-bound community;

determine a probability density function of the length of the time window of the first time-bound community based on the expectation of the length of the time window of the first time-bound community;

obtain a length of a target time window of the first time-bound community by sampling the probability density function of the length of the time window of the first time-bound community;

obtain a starting time of the target time window of the first time-bound community by sampling based on the length of the target time window of the first time-bound community and a preset time range; and

determine the target time window of the first time-bound community based on the starting time of the target time window of the first time-bound community and the length of the target time window of the first time-bound community;

construct an index structure that is transferable between different time-bound communities, and generate, based on the nodes included in respective time-bound communities, the time windows of respective time-bound communities, and the index structure, temporal edges within each of the plurality of time-bound communities and/or temporal edges between the different time-bound communities of the plurality of time-bound communities; and

generate a temporal graph of the target scenario based on the nodes included in each of the plurality of time-bound communities, the time window of each of the plurality of time-bound communities, and the temporal edges within each of the plurality of time-bound communities and/or the temporal edges between the different time-bound communities of the plurality of time-bound communities.

9 . An electronic apparatus, comprising:

a processor; and

a memory for storing processor executable instructions,

wherein the processor is configured to:

group a set of nodes in a target scenario to obtain nodes included in each of a plurality of time-bound communities, wherein the time-bound community represents a community that is in active status for a period of time and eventually goes extinct; and numbers of nodes included in the plurality of time-bound communities follow a power-law distribution;

generate a time window for each of the plurality of time-bound communities, wherein starting times of the time windows corresponding to the plurality of time-bound communities follow a uniform distribution, and lengths of the time windows corresponding to the plurality of time-bound communities follow a power-law distribution, wherein the processor being configured to generate the time window for each of the plurality of time-bound communities comprises the processor being configured to:

determine an expectation of a length of a time window of a first time-bound community based on a number of nodes included in the first time-bound community;

determine a probability density function of the length of the time window of the first time-bound community based on the expectation of the length of the time window of the first time-bound community;

obtain a length of a target time window of the first time-bound community by sampling the probability density function of the length of the time window of the first time-bound community;

obtain a starting time of the target time window of the first time-bound community by sampling based on the length of the target time window of the first time-bound community and a preset time range; and

determine the target time window of the first time-bound community based on the starting time of the target time window of the first time-bound community and the length of the target time window of the first time-bound community;

construct an index structure that is transferable between different time-bound communities, and generate, based on the nodes included in respective time-bound communities, the time windows of respective time-bound communities, and the index structure, temporal edges within each of the plurality of time-bound communities and/or temporal edges between the different time-bound communities of the plurality of time-bound communities; and

generate the temporal graph of the target scenario based on the nodes included in each of the plurality of time-bound communities, the time window of each of the plurality of time-bound communities, and the temporal edges within each of the plurality of time-bound communities and/or the temporal edges between the different time-bound communities of the plurality of time-bound communities.