
	Index = 1;
	For (entity_id in CALCULATIONS)
	{
	If (mod(index, RELS) = 0)
	{
	UPDATE CALCULATIONS
	SET LEVEL = LEVEL + 1
	WHERE ENTITY_ID = entity_id;
	}
	Index = index + 1;
	}

In the current example, every second entry (because RELS=2) is incremented, thus:


	LEVEL	ENTITY_ID

	0	1
	1	2
	0	3
	1	4
	0	5
	1	6
	0	7
	1	8
	0	9
	1	10
	0	11
	1	12
	0	13
	1	14
	0	15
	1	16
	0	17

Next, it is determined how many entities were incremented in the previous operation. That is, the entries having level value one are identified. For example, the following pseudo-code illustrates operations performed on the calculations table:


SELECT count FROM CALCULATIONS WHERE LEVEL = 1;
If (count > RELS)
{
LEVEL = LEVEL + 1;
CALCULATIONS = SELECT * FROM CALCULATIONS
WHERE LEVEL = LEVEL;
Do first step again
}

If the number of such entries is equal to or greater than RELS, then incrementing continues. Here,

entries

2, 4, 6, 8, 10, 12, 14 and 16 (eight entries) were incremented, so the process continues by again selecting every Nth entry among those. That is, in this example, every second one of the recently incremented entries is selected, and again incremented by one. This creates the following calculations table:


	LEVEL	ENTITY_ID

	0	1
	1	2
	0	3
	2	4
	0	5
	1	6
	0	7
	2	8
	0	9
	1	10
	0	11
	2	12
	0	13
	1	14
	0	15
	2	16
	0	17

That is,

entries

4, 8, 12 and 16 (four entries) were incremented this time. Because four is equal to or greater than RELS in this example (RELS=2), the incrementing continues. That is, every second one of the most recently incremented entries (i.e., those with level value equal to two) is again incremented by one, so that the calculations table becomes:


	LEVEL	ENTITY_ID

	0	1
	1	2
	0	3
	2	4
	0	5
	1	6
	0	7
	3	8
	0	9
	1	10
	0	11
	2	12
	0	13
	1	14
	0	15
	3	16
	0	17

That is,entries 8 and 16 (two entries) were incremented this time. Because two is equal to or greater than RELS in this example (RELS=2), the incrementing continues. That is, every second one of the most recently incremented entries (i.e., those with level value equal to three) is again incremented by one, so that the calculations table becomes:


	LEVEL	ENTITY_ID

	0	1
	1	2
	0	3
	2	4
	0	5
	1	6
	0	7
	3	8
	0	9
	1	10
	0	11
	2	12
	0	13
	1	14
	0	15
	4	16
	0	17

That is,entry 16 is incremented this time. Because one entry is not equal to or greater than RELS in this example (RELS=2), the incrementing stops at this point and the calculations table204.

Next, the entry or entries having the maximum level number are identified. In this example,entity 16 has the highest level value (equal to four). Based on that maximum level number, the next lower level number (in this example, three) is sought. Particularly, the process seeks to identify RELS number of entities having the next lower level value. In this example,only entity 8 has a level value equal to three. Therefore, a corresponding entry is made in the relations table206 toassociate entity 8 withentity 16. For example, the following pseudo-code illustrates operations performed on the relations table:


	For (entity in entities_under_me)
	{
	INSERT INTO RELATIONS (SOURCE, TARGET)
	VALUES (entity_above, entity);
	}

The relations table can then contain the following:


	TARGET	SOURCE

	8	16

Next, the process takes each entity with that level value (three in this example) and looks for RELS number of entities have the next lower level value. In this example, that lower level value is two, and the

entries

12 and 4 have that level value. Thus, the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8

Next, the process takes each entity with that level value (two in this example) and looks for RELS number of entities have the next lower level value. In this example, that lower level value is one, and the

entries

2, 6, 10 and 14 have that level value. Of those, two are selected and the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12

Next, the process takesentity 4, which also has level value two, and selects the remaining entries that have the next lower level value, so that the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4

Having checked that there are no unassigned entities with the current level value (that is all entries with level value one have been assigned), the process moves to the next lower level value, which in this example is zero. It does so by four iterations over the respective entities with level value one (that is,

entities

2, 6, 10 and 14). Here, because RELS=2, two entities are identified in a first iteration and the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4
	1	2
	3	2

In a second iteration, two additional entries with level value zero are found and the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4
	1	2
	3	2
	5	6
	7	6

In a third iteration, two additional entries with level value zero are found and the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4
	1	2
	3	2
	5	6
	7	6
	9	10
	11	10

In a fourth iteration, two additional entries with level value zero are found and the relations table becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4
	1	2
	3	2
	5	6
	7	6
	9	10
	11	10
	13	14
	15	14

In this example, after the iterations over all entities with level value one are complete, one entity with level value zero remains (entity 17). That entity is then assigned to the last entity that has level value one, and the relations table finally becomes:


	TARGET	SOURCE

	8	16
	12	8
	4	8
	2	12
	6	12
	10	4
	14	4
	1	2
	3	2
	5	6
	7	6
	9	10
	11	10
	13	14
	15	14
	17	14

FIG. 3 shows an example of amodel entity network300. Particularly, themodel entity network300 can be generated as a visual representation based on the above example. Themodel entity network300 includes the 17 entities organized based on the parameter RELS=2, meaning that each entity should have up to two other entities assigned to it. The single exception to that rule in the current example is that three entities (

numbers

13, 15 and 17) are assigned to theentity 14. Nevertheless, themodel entity network300 is a balanced and useful model that can be analyzed to gain insight into the nature of a real entity network (e.g., a social network).

FIG. 4 shows an example of using amodel entity network400 to analyze areal entity network402. First, there will be described an example of generating themodel entity network400 and thereafter the analysis will be exemplified.

In this example, the parameters ENTS=17 and RELS=3 are received. The processing essentially continues by: assigning a lowest level value to all entities (e.g., level value zero); incrementing every Nth entity (where N=RELS=3) by one; because the incremented entities are equal to or greater than RELS, every Nth entity of them is again incremented (to level value two); and because only one entity is incremented in the most recent step, the incrementing ends. At that point, the calculation table204 (FIG. 2) is compete and may contain:


	LEVEL	ENTITY_ID

	0	1
	0	2
	1	3
	0	4
	0	5
	1	6
	0	7
	0	8
	2	9
	0	10
	0	11
	1	12
	0	13
	0	14
	1	15
	0	16
	0	17

Next, the maximum level value is found (equal to two in this example), which is assigned toentity 9, and the next lower value is identified (i.e., level value one). For RELS number of entities having this number, a corresponding relation is entered in the relations table206 (FIG. 2). Because no additional entities have the maximum value, the check continues with the next lower level value, and one unassigned entity is found (namely entity 15). This entity is inserted under the entity that most recently had an entity assigned to it (i.e., entity 9).

The process is then repeated for the level value one until all entities in the entities table202 (FIG. 2) occur in the TARGET column of the relations table; that is, until every entity (except the top entity) has a relation to one entity above it. The relation table at that point may contain the following for the model entity network400:


	TARGET	SOURCE

	3	9
	6	9
	12	9
	15	9
	1	3
	2	3
	4	3
	5	6
	7	6
	8	6
	10	12
	11	12
	13	12
	14	15
	16	15
	17	15

That is, themodel entity network400 includes the 17 entities organized based on the parameter RELS=3, meaning that each entity should have up to three other entities assigned to it. The single exception to that rule in the current example is that four entities (numbers 3, 6, 12 and 15) are assigned to theentity 9. Nevertheless, themodel entity network400 is a balanced and useful model that can be analyzed to gain insight into the nature of thereal entity network402.

In some implementations, theanalysis component116 can compare the

networks

400 and402 and produce one or more analysis results. For example, it can be observed that in thereal entity network402, the entity 6 may be redundant; for example, perhaps entity 3 could be related directly to theentity 9 instead. As another example, it can be observed that theentity 15 does not have any entities below it, so that an asymmetry exists with regard to the other entity (number 6) that has a similar position in the network. The entity 3, on the other hand may be considered overcrowded given the target to have three relations per entity, as may theentity 12. As another example, thereal entity network402 is seen to have five levels, whereas themodel entity network400 has three levels. Other analysis can be performed.

In some implementations, one wishes to store data from an existing entity network (e.g., Facebook or LinkedIn) and either analyze or display that data. Particularly, tests should be performed on the structure of the social network, preferably without using the actual data of individuals, due to privacy concerns and other reasons. Therefore suitable metadata about fictitious entities can be assembled and stored in the entities table202 (FIG. 2), for example using theinput module112A (FIG. 1), and this non-personal data (e.g., demographics, images, audio, video, text, etc.) can then be part of the analysis. For example, the metadata can be selected so that it approximately represents the variety of data occurring in the real entity network. That is, with knowledge about how many entities are registered in a particular entity network and the number of connections per entry (e.g., the number of friends in Facebook), a model entity network can be created that resembles the actual entity network for testing purposes.

FIG. 5 is a schematic diagram of ageneric computer system500. Thesystem500 can be used for the operations described in association with any of the computer-implement methods described previously, according to one implementation. Thesystem500 includes aprocessor510, amemory520, astorage device530, and an input/output device540. Each of the

components

510,520,530, and540 are interconnected using a system bus550. Theprocessor510 is capable of processing instructions for execution within thesystem500. In one implementation, theprocessor510 is a single-threaded processor. In another implementation, theprocessor510 is a multi-threaded processor. Theprocessor510 is capable of processing instructions stored in the memory420 or on thestorage device530 to display graphical information for a user interface on the input/output device540.

Thememory520 stores information within thesystem400. In some implementations, thememory520 is a computer-readable medium. Thememory520 is a volatile memory unit in some implementations and is a non-volatile memory unit in other implementations.

Thestorage device530 is capable of providing mass storage for thesystem500. In one implementation, thestorage device530 is a computer-readable medium. In various different implementations, thestorage device530 may be a floppy disk device, a hard disk device, an optical disk device, or a tape device.

The input/output device540 provides input/output operations for thesystem500. In one implementation, the input/output device540 includes a keyboard and/or pointing device. In another implementation, the input/output device540 includes a display unit for displaying graphical user interfaces.

The features described can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The apparatus can be implemented in a computer program product tangibly embodied in an information carrier, e.g., in a machine-readable storage device, for execution by a programmable processor; and method steps can be performed by a programmable processor executing a program of instructions to perform functions of the described implementations by operating on input data and generating output. The described features can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. A computer program is a set of instructions that can be used, directly or indirectly, in a computer to perform a certain activity or bring about a certain result. A computer program can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment.

Suitable processors for the execution of a program of instructions include, by way of example, both general and special purpose microprocessors, and the sole processor or one of multiple processors of any kind of computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memories for storing instructions and data. Generally, a computer will also include, or be operatively coupled to communicate with, one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits).

To provide for interaction with a user, the features can be implemented on a computer having a display device such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor for displaying information to the user and a keyboard and a pointing device such as a mouse or a trackball by which the user can provide input to the computer.

The features can be implemented in a computer system that includes a back-end component, such as a data server, or that includes a middleware component, such as an application server or an Internet server, or that includes a front-end component, such as a client computer having a graphical user interface or an Internet browser, or any combination of them. The components of the system can be connected by any form or medium of digital data communication such as a communication network. Examples of communication networks include, e.g., a LAN, a WAN, and the computers and networks forming the Internet.

The computer system can include clients and servers. A client and server are generally remote from each other and typically interact through a network, such as the described one. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of this disclosure. Accordingly, other implementations are within the scope of the following claims.

Claims

What is claimed is:

1. A computer-implemented method for analyzing an entity network, the method comprising:

receiving input including a first number (E) corresponding to a number of entities in a real entity network to be analyzed, and a second number (R) corresponding to a number of relations per entity in the real entity network;

in response to the input, generating (i) E number of entity entries in an entities table, each entity entry including at least an entity identifier and entity metadata, and (ii) a calculations table including the E number of entity identifiers, each associated with a level value of zero;

incrementing every Rth level value in the calculations table by one;

determining, using one or more processors, whether more than R number of the level values were incremented in a most recent incrementing step, and if so again performing the incrementing step on those level values, wherein such incrementing and determination are repeated until the determination finds at most R number of recently incremented level values;

after the incrementing is finished, creating a model entity network that have the E number of entity entries organized according to their respective level values, the model entity network created by generating a relations table with associations between the E number of entity entries;

performing one or more tests on the generated model entity network that involve at least some of the metadata; and

modifying the real entity network based on an outcome of the performed test.

2. The computer-implemented method ofclaim 1, further comprising selecting the metadata based on actual data in the real entity network while preserving privacy of the actual data.

3. The computer-implemented method ofclaim 1, wherein creating the model entity network comprises:

identifying a first entity entry in the calculation table as having a maximum level value;

selecting every entity entry in the calculation table whose level value is one less than the maximum level value, until at most R number of entity entries are selected; and

creating relations between each of the selected entity entries and the first entity entry in the relations table.

4. The computer-implemented method ofclaim 3, wherein no other entity entry has the maximum level value and the method further comprises determining whether any unselected entity entry also has the level value that is one less than the maximum level value, and if so creating a relation between that unselected entry and the first entity entry in the relations table.

5. The computer-implemented method ofclaim 2, wherein performing the one or more tests comprises determining whether an asymmetry exists in the real entity network.

6. The computer-implemented method ofclaim 2, wherein performing the one or more tests comprises determining whether a redundancy exists in the real entity network.

7. The computer-implemented method ofclaim 2, wherein performing the one or more tests comprises determining whether overcrowding exists in the real entity network.

8. A computer program product tangibly embodied in a computer-readable storage medium and comprising instructions that when executed by a processor perform a method comprising:

incrementing every Rth level value in the calculations table by one;

modifying the real entity network based on an outcome of the performed test.

9. The computer program product ofclaim 8, the method further comprising selecting the metadata based on actual data in the real entity network while preserving privacy of the actual data.

10. The computer program product ofclaim 8, wherein creating the model entity network comprises:

11. The computer program product ofclaim 10, wherein no other entity entry has the maximum level value and the method further comprises determining whether any unselected entity entry also has the level value that is one less than the maximum level value, and if so creating a relation between that unselected entry and the first entity entry in the relations table.

12. The computer program product ofclaim 10, wherein performing the one or more tests comprises determining whether an asymmetry exists in the real entity network.

13. The computer program product ofclaim 10, wherein performing the one or more tests comprises determining whether a redundancy exists in the real entity network.

14. The computer program product ofclaim 10, wherein performing the one or more tests comprises determining whether overcrowding exists in the real entity network.

15. A system comprising:

one or more processors; and

a computer program product comprising instructions that when executed perform a method comprising:

incrementing every Rth level value in the calculations table by one;

modifying the real entity network based on an outcome of the performed test.

16. The system ofclaim 15, wherein creating the model entity network comprises:

17. The system ofclaim 16, wherein no other entity entry has the maximum level value and the method further comprises determining whether any unselected entity entry also has the level value that is one less than the maximum level value, and if so creating a relation between that unselected entry and the first entity entry in the relations table.

18. The system ofclaim 16, wherein performing the one or more tests comprises determining whether an asymmetry exists in the real entity network.

19. The system ofclaim 16, wherein performing the one or more tests comprises determining whether a redundancy exists in the real entity network.

20. The system ofclaim 16, wherein performing the one or more tests comprises determining whether overcrowding exists in the real entity network.