Clustering spatio-temporal bi-partite graphs for finding crowdsourcing communities in IoMT networks

Figures & data

Figure 1. Process example of resource allocation for X nodes: (a) the bi-partite graph, (b) the X and Y projections, and (c) the number of common neighbours in Y and X – Source Zhou et al. (2007)

Figure 2. Room with IoT infrastructure and possible service components – Source Cisco Systems (2009)

Figure 3. Possible data flows between different service components

Figure 4. Bi-partite graph representing IoT devices and service components of a smart home environment

Figure 5. Two-tier infrastructure represented as a bi-partite graph

Figure 6. Comparison of community detection algorithms – Source Papadopoulos et al. (2011)

Table 1. Steps to allocate d_min according to the current velocities of IoMT devices

GIVEN the location of all the IoMT devices and their respective velocities in TWi

FOR each parent data point Pi and another data point Pj

IF velocity of Pi and Pj is less than vi

FIND the neighbours with dmin ≤ di

Figure 7. An example of a bi-partite graph based on mobility relationships between neighbours

Table 2. Steps to create a bi-partite graph

GIVEN all the data points at a given time window

FOR each parent data point

COMPUTE dmin between the parent data point and other data points

IF dmin < specified user threshold

CREATE edge between parent data point and the other data point

Table 3. Steps to find communities in IoMT networks

GIVEN a bi-partite graph network

INITIATE by placing every node into its own community

FOR each node

replace node to neighbouring community

recalculate modularity

IF modularity increases

replace device into a new community

ELSE

Keep node in current community

COMBINE communities into new nodes, using self-weights and weighted edges

REPEAT loop above until modularity is optimized

Figure 8. US highway 101 segment used for our real-world scenario

Table 4. Example of IoMT data collected by a smart car

Smart Car ID	Epoch Time (milliseconds)	Global X (meters)	Global Y (meters)	Velocity (meter/second)
2	1,118,846,980,300.00	6,451,140.33	1,873,342.00	40.00
2	1,118,846,980,400.00	6,451,143.02	1,873,339.04	40.00
2	1,118,846,980,500.00	6,451,145.71	1,873,336.08	40.00
2	1,118,846,980,600.00	6,451,148.40	1,873,333.12	40.00
2	1,118,846,980,700.00	6,451,151.08	1,873,330.15	40.00
2	1,118,846,980,800.00	6,451,153.77	1,873,327.19	40.00
2	1,118,846,980,900.00	6,451,156.46	1,873,324.23	40.02
2	1,118,846,981,000.00	6,451,159.15	1,873,321.27	40.03
2	1,118,846,981,100.00	6,451,161.84	1,873,318.31	39.93
2	1,118,846,981,200.00	6,451,164.55	1,873,315.32	39.61
2	1,118,846,981,300.00	6,451,167.20	1,873,312.38	39.14
2	1,118,846,981,400.00	6,451,169.80	1,873,309.53	38.61
2	1,118,846,981,500.00	6,451,172.36	1,873,306.72	38.28
2	1,118,846,981,600.00	6,451,174.96	1,873,303.87	38.42
2	1,118,846,981,700.00	6,451,177.61	1,873,300.93	38.78
2	1,118,846,981,800.00	6,451,180.34	1,873,297.92	38.92
2	1,118,846,981,900.00	6,451,182.98	1,873,294.96	38.54
2	1,118,846,982,000.00	6,451,185.54	1,873,292.12	37.51
2	1,118,846,982,100.00	6,451,188.02	1,873,289.41	36.34
2	1,118,846,982,200.00	6,451,190.42	1,873,286.82	35.50
2	1,118,846,982,300.00	6,451,192.76	1,873,284.25	35.08
2	1,118,846,982,400.00	6,451,195.11	1,873,281.66	34.96
2	1,118,846,982,500.00	6,451,197.46	1,873,279.07	34.98
2	1,118,846,982,600.00	6,451,199.81	1,873,276.47	35.00
2	1,118,846,982,700.00	6,451,202.17	1,873,273.88	34.99

Figure 9. Example of a bi-partite graph of smart vehicles and their neighbours moving on highway

Table 5. Overview of the community detection results

	5 m	10 m	15 m	20 m	25 m	50 m	Modifiable
Community level
Total number of communities	2943	25650	9842	6312	5099	3421	9450
Maximum number of communities	68	52	22	13	10	6	28
Mean number of communities every second	40	35	13	9	7	5	13
Standard Deviation	9.51	6.62	2.69	1.54	1.18	0.75	3.40
Mean Modularity	0.97	0.92	0.84	0.77	0.72	0.60	0.82
Community composition for every second
Minimum number of smart cars per community	1	1	1	1	1	1	1
Maximum number of smart cars per community	10	51	69	84	102	128	74
Mean number of smart cars per community	2	6	19	29	36	57	19
Mean velocity of smart cars (m/s)	12	13	13	13	13	13	12
Mean variance of velocity of smart cars	0.91	3.49	5.55	5.86	6.12	6.85	4.91

Figure 10. Sequential snapshots of the evolving communities with d_min = 25 m

Figure 11. Number of connected vehicles discovered in each community (i.e. cluster)

Figure 12. Number of smart cars discovered in each community for modifiable d_min.

Figure 13. Number of communities on the highway over time

Figure 14. Number of communities on the highway for modifiable mobility neighbourhoods

Figure 15. Sample of the generated silhouette index values

Zhou, T., Ren, J., Medo, M., & Zhang, Y. C. (2007). Bi-partite network projection and personal recommendation. Physical Review E, 76(4), 046115.

 Google Scholar

Cisco Systems. (2009). Cisco cloud computing – data center strategy, architecture, and solutions. Point of View White Paper for U.S Public Sector.

 Google Scholar

Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. (2011). Community detection in social media. Data Mining and Knowledge Discovery, 24(3), 515–554.

 Google Scholar

Data availability statement

The data that support the findings of this study are openly available in Next Generation Simulation (NGSIM) Vehicle Trajectories and Supporting Data (opendatanetwork.com) at https://www.opendatanetwork.com/dataset/data.transportation.gov/.